论文标题
L形平面图的理论
A Theory of L-shaped Floor-plans
论文作者
论文摘要
现有的图理论方法主要局限于具有矩形边界的地板图。在本文中，我们引入了具有$ L $形边界的地板图（边界只有一个凹角）。为了确保L形边界，我们介绍了地板平面的非平凡性概念。如果无法减少凹角的数量，而不会影响其中的模块邻接，则具有至少一个凹角的直线边界的地板平面面板是不平凡的。此外，我们为存在与适当三角形的平面图（PTPG）$ g $相对应的非平凡的L形地板平面图提供了必要和充分的条件。另外，如果存在，我们为其构建而开发了$ O（n^2）$算法。
Existing graph theoretic approaches are mainly restricted to floor-plans with rectangular boundary. In this paper, we introduce floor-plans with $L$-shaped boundary (boundary with only one concave corner). To ensure the L-shaped boundary, we introduce the concept of non-triviality of a floor-plan. A floor-plan with a rectilinear boundary with at least one concave corner is non-trivial if the number of concave corners can not be reduced, without affecting the modules adjacencies within it. Further, we present necessary and sufficient conditions for the existence of a non-trivial L-shaped floor-plan corresponding to a properly triangulated planar graph (PTPG) $G$. Also, we develop an $O(n^2)$ algorithm for its construction, if it exists.
