Linear-time algorithm for generating L-shaped floorplans using canonical ordering technique

Shiksha (), Krishnendra Shekhawat, Ritu Chandna and Akshaj Gupta
Additional contact information
Shiksha: BITS Pilani, Pilani Campus
Krishnendra Shekhawat: BITS Pilani, Pilani Campus
Ritu Chandna: BITS Pilani, Pilani Campus
Akshaj Gupta: BITS Pilani, Pilani Campus

Journal of Combinatorial Optimization, 2025, vol. 49, issue 4, No 12, 35 pages

Abstract: Abstract L-shaped floorplans are defined by rectangular modules enclosed within a rectilinear outer boundary, forming an L-shape that can not be altered through simple extension or contraction of a boundary wall. The boundary of such floorplans comprises five convex corners and one concave corner. The concave corner on the boundary of the plan can not be converted into a convex corner without altering the horizontal and vertical adjacency among the modules. This paper introduces a linear-time algorithm based on canonical ordering to generate L-shaped floorplans from properly triangulated plane graphs (PTPGs). Here, modules in the floorplan correspond to the nodes of the given graph, while edges in the graph represent wall adjacency between modules. The proposed algorithm assigns a unique labeling to the given graph, ensuring the presence of a concave corner on the resulting floorplan’s boundary. Simple boundary wall extensions or contractions cannot eliminate this concave corner. It also produces multiple L-shaped floorplans corresponding to the given PTPG, with variations mainly on their concave corners, highlighting the unique configurations possible within the same boundary constraints. Our algorithm offers simplicity over existing methods and is easy to implement. Additionally, we have implemented the algorithm in Python, enabling easy integration for generating L-shaped floorplans in various architectural and VLSI circuit design applications.

Keywords: Adjacency; Graph theory; Algorithm; Concave corner; Non-rectangular floorplan; Python implementation (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01287-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:4:d:10.1007_s10878-025-01287-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01287-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().