A theory of L-shaped floor-plans.

Existing graph-theoretic approaches to construct floor-plans for a given plane graph are mainly restricted to floor-plans with rectangular boundary. This paper introduces 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. Further, we present necessary and sufficient conditions for the existence of a non-trivial L -shaped floor-plan corresponding to a properly triangulated plane graph (PTPG) G. Also, we develop an O (n 3) algorithm for its construction, if it exists. • Construction of floorplans for a given graph is limited to rectangular boundaries. • We proposed the existence and construction of L-shaped floorplans. • Obtained L-shaped floorplans cannot be transformed into rectangular floorplans. [ABSTRACT FROM AUTHOR]