A Theory of L-shaped Floor-plans

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.