pith. sign in

arxiv: 2606.21159 · v1 · pith:PN7Y4XUZnew · submitted 2026-06-19 · 💻 cs.CG · cs.GR· cs.RO· math.CO

DPLAN: Minimal Connectivity to Floorplan Generation

Rohit Lohani , Krishnendra Shekhawat This is my paper

Pith reviewed 2026-06-26 12:59 UTC · model grok-4.3

classification 💻 cs.CG cs.GRcs.ROmath.CO
keywords floor plan generationdoor connectivitynon-adjacency constraintsgraph triangulationrectangular floor plansorthogonal floor plansplane graphscomputational geometry
0
0 comments X

The pith

DPLAN generates valid rectangular or orthogonal floor plans from door connections and non-adjacency constraints by minimally connecting the graph and removing separating triangles from a bi-connected plane triangulation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out a graph-based procedure to turn abstract user constraints into concrete floor plans. It first inspects the room-and-door graph and adds the fewest edges needed to make it connected. It then builds a bi-connected plane triangulation of that graph to guarantee a layout without overlaps or empty spaces. Finally it strips away separating triangles, either by edge changes alone for rectangular plans or by inserting vertices for orthogonal plans, so that every required door exists and every forbidden adjacency is avoided. A reader would care because the method supplies an explicit algorithmic path from high-level rules to a drawable layout.

Core claim

Any set of door and non-adjacency constraints can be realized as a non-overlapping floor plan: augment the constraint graph minimally to restore connectivity, form a bi-connected plane triangulation, then delete separating triangles by edge modification (for rectangular floor plans) or by vertex insertion (for orthogonal floor plans) while leaving the original constraints intact.

What carries the argument

The bi-connected plane triangulation of the minimally augmented constraint graph, followed by controlled removal of separating triangles to obtain either a rectangular or orthogonal floor plan.

If this is right

  • All user-specified door connections appear as shared walls and all forbidden adjacencies are prevented.
  • Rectangular floor plans contain no extra rooms or unused spaces.
  • Orthogonal floor plans can accommodate rectilinear room shapes through the added vertices.
  • The same constraint set can produce either a rectangular or an orthogonal layout depending on the chosen triangle-removal rule.
  • The output layouts can be rendered directly from the final graph in an interactive Python tool.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same augmentation-plus-triangulation pipeline could be reused for other adjacency-constrained layout problems such as circuit placement or facility design.
  • Room dimensions and area requirements could be assigned after the topology is fixed, turning the current method into the first stage of a two-stage pipeline.
  • Non-rectangular plot boundaries would require a modified triangulation step that respects the outer polygon rather than assuming a rectangle.
  • Circulation paths could be enforced by adding extra edges that represent mandatory corridors before the triangulation stage.

Load-bearing premise

A bi-connected plane triangulation of the minimally augmented graph can always be converted into a valid non-overlapping floor plan that keeps every original door requirement and every non-adjacency while introducing neither extra rooms nor empty spaces.

What would settle it

A concrete list of rooms, required doors, and forbidden adjacencies for which the DPLAN procedure either outputs an overlapping layout, creates an extra room, or violates a non-adjacency, yet a valid floor plan is known to exist.

Figures

Figures reproduced from arXiv: 2606.21159 by Krishnendra Shekhawat, Rohit Lohani.

Figure 1
Figure 1. Figure 1: Flowchart of the DPLAN pipeline from minimal door-connectivity input (with non-adjacency constraints) to RFP/OFP generation [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) Minimal input graph with non-adjacency constraints. (b) A plane triangulated graph constructed using the proposed approach. (c) A properly triangulated plane graph obtained from the proposed approach. (d) Orthogonal floor plans generated from the resulting PTG. (e) Rectangular floor plans generated from the resulting PTPG [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (b) Rectangular floor plan based on the graph in (a); (c) non-rectangular floor plan derived from the same graph; (e) orthogonal floor plan generated from the graph in (d). 2 Terminologies This section introduces the basic concepts and terminology used in this study. These definitions provide a clear foundation for representing and analyzing floor plans using graph structures and spatial relationships [PI… view at source ↗
Figure 4
Figure 4. Figure 4: Visual comparison of inputs and generated outputs using our method, HouseGAN++, and Graph2Plan [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a-e) Construction of a connected graph GC while preserving the specified input constraints [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: (a-e) Construction of a Bi-connectivity graph GB while preserving the specified input constraints [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Additional space is created in the floor plan corresponding to the graph with a non-triangular face (1,2,3,4). of the current cycle, and a pointer e is set to s. At each step, the function Get Next Edge(e, GB) returns the next edge in the cyclic order around the current vertex, according to the fixed planar embedding. If the returned edge equals the starting edge s, the traversal of the face is complete, a… view at source ↗
Figure 8
Figure 8. Figure 8: (a-h) Construction of a bi-connected triangulation graph GT while preserving the specified input constraints [PITH_FULL_IMAGE:figures/full_fig_p023_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: A non-rectangular room (Room 1) appears in the floor plan due to the presence of a separating triangle (1,2,3) in the input graph. exactly two triangular faces and is therefore an exterior edge of T ; in that case the edge is removed from ET , the list of separating triangles is recomputed as T ← ST(GT ), the counter m is replaced by the new value m′ = |T |, and removed is set to true. The algorithm then g… view at source ↗
Figure 10
Figure 10. Figure 10: (a-f) Breaking of separating triangles [PITH_FULL_IMAGE:figures/full_fig_p027_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: (a-k) Multiple Rectangular Floor plans generated based on the previously generated graph GF [PITH_FULL_IMAGE:figures/full_fig_p028_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: (a-m) Multiple orthogonal Floor plans generated based on the previously generated graph GT [PITH_FULL_IMAGE:figures/full_fig_p029_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: (a–c) Customized two-bedroom residential floor plans obtained through user-guided refinement of the generated layouts [PITH_FULL_IMAGE:figures/full_fig_p031_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: (a–d) Customized three-bedroom residential floor plans obtained through user-guided refinement of the generated layouts [PITH_FULL_IMAGE:figures/full_fig_p032_14.png] view at source ↗
read the original abstract

Automated floor plan generation is an important problem in computational architectural design. The goal is to construct a floor plan from user-defined room numbers and door requirements. The user specifies which rooms must share a door and which rooms must not be adjacent. However, these requirements do not determine the exact placement or shape of the rooms. The task is therefore to arrange the rooms in a single floor plan so that all required door connections are satisfied and no rooms overlap. To address this problem, we propose DPLAN (Door Connectivity to Floor Plan Generation), a graph-based prototype that generates floor plans from door and non-adjacency constraints. The framework operates in three stages. First, the user-defined graph is examined and, if disconnected, additional edges are added to connect its components. Second, a bi-connected plane triangulation is constructed to ensure the existence of a floor plan without overlapping rooms or empty spaces. Third, the triangulated graph is transformed into floor plans. For rectangular floor plans (RFPs), separating triangles are removed by modifying edges without adding new vertices, thereby avoiding the creation of extra rooms. For orthogonal floor plans (OFPs), separating triangles are removed by introducing additional vertices, allowing rectilinear room shapes. By enforcing both door and non-adjacency requirements, the framework generates floor plans that satisfy the given constraints. The method is implemented in Python and includes a prototype for interactive constraint specification and floor plan visualization. Currently, the framework supports rectangular plot boundaries. Future work includes support for non-rectangular plots, dimension-based scaling, and circulation modeling.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes DPLAN, a three-stage graph-based prototype for automated floorplan generation. It takes user-specified room counts with door (adjacency) and non-adjacency constraints, augments disconnected graphs by adding edges, constructs a bi-connected plane triangulation, and transforms the result into rectangular floor plans (RFPs) via edge modification or orthogonal floor plans (OFPs) via vertex insertion to eliminate separating triangles, claiming the output satisfies all constraints without overlaps or extra rooms.

Significance. If the transformation from bi-connected plane triangulation to RFP/OFP can be shown to preserve exactly the input adjacencies and non-adjacencies, the work would supply a constructive graph algorithm for a classic problem in computational geometry and architectural design automation. The Python implementation with interactive visualization is noted as a practical contribution, but the absence of any validation, examples, or proofs in the manuscript prevents assessing whether the result holds.

major comments (2)
  1. [Abstract] Abstract, third-stage description: the central claim that removing separating triangles (edge modification for RFPs, vertex insertion for OFPs) from the bi-connected plane triangulation always yields valid non-overlapping floor plans that preserve all original door connections and exclude all forbidden non-adjacencies is unsupported; no algorithm, invariant, or counterexample discussion is supplied to establish that the step does not introduce new adjacencies or extra rooms.
  2. No validation section or results: the manuscript states that the framework 'generates floor plans that satisfy the given constraints' and mentions a Python implementation, yet provides no worked examples, failure cases, metrics (e.g., constraint satisfaction rate), or comparison against existing floorplan generators, leaving the soundness of the pipeline unverified.
minor comments (2)
  1. [Abstract] The abstract lists future work (non-rectangular plots, dimension scaling, circulation) but does not discuss current limitations such as restriction to rectangular boundaries or handling of degenerate graphs.
  2. Notation for the input graph (vertices as rooms, edges as doors) is introduced informally; a formal definition in an early section would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive report. We address the two major comments point by point below and commit to revisions that strengthen the manuscript without altering its core claims.

read point-by-point responses

  1. Referee: [Abstract] Abstract, third-stage description: the central claim that removing separating triangles (edge modification for RFPs, vertex insertion for OFPs) from the bi-connected plane triangulation always yields valid non-overlapping floor plans that preserve all original door connections and exclude all forbidden non-adjacencies is unsupported; no algorithm, invariant, or counterexample discussion is supplied to establish that the step does not introduce new adjacencies or extra rooms.

    Authors: We acknowledge that the current manuscript presents the third stage at a high level and does not supply explicit invariants, a formal algorithm description, or counterexample analysis for the separating-triangle removal step. The operations are intended to maintain the input adjacencies by construction (edge modification for RFPs avoids new rooms; vertex insertion for OFPs adds only auxiliary vertices), yet this is not demonstrated in the text. In the revision we will add a dedicated subsection detailing the local modifications, the preserved adjacency relation, and a brief argument that no forbidden adjacencies are created. revision: yes

  2. Referee: [—] No validation section or results: the manuscript states that the framework 'generates floor plans that satisfy the given constraints' and mentions a Python implementation, yet provides no worked examples, failure cases, metrics (e.g., constraint satisfaction rate), or comparison against existing floorplan generators, leaving the soundness of the pipeline unverified.

    Authors: The manuscript indeed contains no empirical validation, worked examples, or quantitative metrics; it is presented as a graph-theoretic prototype. We agree that this omission makes it difficult to assess correctness in practice. The revision will incorporate a new section with at least two concrete input graphs, the generated floor plans, and a discussion of constraint preservation, together with a short note on known limitations. revision: yes

Circularity Check

0 steps flagged

No circularity; constructive graph algorithm is self-contained

full rationale

The paper presents a three-stage algorithmic procedure (graph augmentation for connectivity, bi-connected plane triangulation, then separating-triangle removal to produce RFPs/OFPs) without equations, fitted parameters, or any self-citation. No step reduces the claimed output to the input by definition or construction; the transformation is asserted as a graph-theoretic construction rather than a renaming or self-referential fit. This matches the reader's assessment that the method is a constructive algorithm with no evident reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on domain assumptions from graph theory about triangulations corresponding to floor plans and on the claim that added edges preserve non-adjacency; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption A bi-connected plane triangulation of the augmented graph guarantees a floor plan without overlaps or empty spaces.
    Invoked in the second stage as the basis for existence of valid layouts.
  • domain assumption Added connecting edges do not violate any user-specified non-adjacency constraints.
    Stated implicitly when the method adds edges to disconnected components.

pith-pipeline@v0.9.1-grok · 5816 in / 1240 out tokens · 23267 ms · 2026-06-26T12:59:11.738278+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

55 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Rectangular duals of planar graphs

    Krzysztof Ko´ zmi´ nski and Edwin Kinnen. Rectangular duals of planar graphs. Networks, 15(2):145–157, 1985

    1985

  2. [2]

    Existence theorems for floorplans

    Ingrid Rinsma. Existence theorems for floorplans. Bulletin of the Australian Mathematical Society , 37(3):473–475, 1988

    1988

  3. [3]

    A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph

    Jayaram Bhasker and Sartaj Sahni. A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph. Networks, 17(3):307–317, 1987

    1987

  4. [4]

    Rectangular and orthogonal floorplans wit h required room areas and tree adjacency

    Ingrid Rinsma. Rectangular and orthogonal floorplans wit h required room areas and tree adjacency. Environment and Planning B: Planning and Design , 15(1):111–118, 1988. b c ef g h i j k l m k ei l k p f i q s t q u g c f e : m k v f q p w c s q x m k e i l k p f i q s t q u g c f ey z i p i h q s m g g h e q l { q v k p v y: (4) (3) | } } ~ € } €  ‚ ƒ „‚...

    1988

  5. [5]

    Algorithms for floorplan d esign via rectangular dualization

    Yen-Tai Lai and Sany M Leinwand. Algorithms for floorplan d esign via rectangular dualization. IEEE transactions on computer-aided design of integrated circuits and systems , 7(12):1278–1289, 1988

    1988

  6. [6]

    Simple and efficient floor-planning

    Maciej Kurowski. Simple and efficient floor-planning. Information processing letters , 86(3):113–119, 2003

    2003

  7. [7]

    Compact flo or-planning via orderly spanning trees

    Chien-Chih Liao, Hsueh-I Lu, and Hsu-Chun Yen. Compact flo or-planning via orderly spanning trees. Journal of Algo- rithms, 48(2):441–451, 2003

    2003

  8. [8]

    Automatic real-t ime generation of floor plans based on squarified treemaps algorithm

    Fernando Marson and Soraia Raupp Musse. Automatic real-t ime generation of floor plans based on squarified treemaps algorithm. International Journal of Computer Games Technology , 2010(1):624817, 2010

    2010

  9. [9]

    Improved floor-plann ing of graphs via adjacency-preserving transformations

    Huaming Zhang and Sadish Sadasivam. Improved floor-plann ing of graphs via adjacency-preserving transformations. Journal of combinatorial optimization , 22(4):726–746, 2011

    2011

  10. [10]

    A Novel Algorithm for Real-time Procedural Generation of Building Floor Plans

    Maysam Mirahmadi and Abdallah Shami. A novel algorithm f or real-time procedural generation of building floor plans. arXiv preprint arXiv:1211.5842 , 2012

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  11. [11]

    Irregular architectural layout synthesis with graphical inputs

    Hao Hua. Irregular architectural layout synthesis with graphical inputs. Automation in construction , 72:388–396, 2016

    2016

  12. [12]

    Customization an d generation of floor plans based on graph transformations

    Xiao-Yu Wang, Yin Yang, and Kang Zhang. Customization an d generation of floor plans based on graph transformations. Automation in Construction , 94:405–416, 2018

    2018

  13. [13]

    Automated generation of dimensioned rectangular floor- plans

    Nitant Upasani, Krishnendra Shekhawat, and Garv Sachde va. Automated generation of dimensioned rectangular floor- plans. Automation in Construction , 113:103149, 2020

    2020

  14. [14]

    A tool for computer-generated dimensioned floorplans based on given adjacencies

    Krishnendra Shekhawat, Nitant Upasani, Sumit Bisht, an d Rahil N Jain. A tool for computer-generated dimensioned floorplans based on given adjacencies. Automation in Construction , 127:103718, 2021

    2021

  15. [15]

    Automated generation of floorplans with non-rectangular rooms

    Krishnendra Shekhawat, Rohit Lohani, Chirag Dasannach arya, Sumit Bisht, and Sujay Rastogi. Automated generation of floorplans with non-rectangular rooms. Graphical Models, 127:101175, 2023

    2023

  16. [16]

    Jain, Riddhesh Jayesh Tiwaskar, and Chinmay Hebbar

    Sumit Bisht, Krishnendra Shekhawat, Nitant Upasani, Ra hil N. Jain, Riddhesh Jayesh Tiwaskar, and Chinmay Hebbar. Transforming an adjacency graph into dimensioned floorplan layouts. Computer Graphics Forum , 41(6):5–22, 2022

    2022

  17. [17]

    Automated generation of housing layouts using graph-rules

    Shiksha, Rohit Lohani, Krishnendra Shekhawat, Arsh Sin gh, and Karan Agrawal. Automated generation of housing layouts using graph-rules. Computers & Graphics , 134:104506, 2026

    2026

  18. [18]

    Floornet: A un ified framework for floorplan reconstruction from 3d scans

    Chen Liu, Jiaye Wu, and Yasutaka Furukawa. Floornet: A un ified framework for floorplan reconstruction from 3d scans. In Proceedings of the European conference on computer vision ( ECCV), pages 201–217, 2018

    2018

  19. [19]

    Data-driven interior plan generation for residential buildings

    Wenming Wu, Xiao-Ming Fu, Rui Tang, Yuhan Wang, Yu-Hao Qi , and Ligang Liu. Data-driven interior plan generation for residential buildings. ACM Transactions on Graphics (TOG) , 38(6):1–12, 2019

    2019

  20. [20]

    Floor-sp: Inverse cad for floorplans by sequential room-wi se shortest path

    Jiacheng Chen, Chen Liu, Jiaye Wu, and Yasutaka Furukawa . Floor-sp: Inverse cad for floorplans by sequential room-wi se shortest path. In Proceedings of the IEEE/CVF International Conference on Co mputer Vision (ICCV) , October 2019

    2019

  21. [21]

    Graph2plan: learning floorplan generation from layout graphs

    Ruizhen Hu, Zeyu Huang, Yuhan Tang, Oliver Van Kaick, Hao Zhang, and Hui Huang. Graph2plan: learning floorplan generation from layout graphs. ACM Trans. Graph. , 39(4), August 2020

    2020

  22. [22]

    House-gan: Relational generative adversarial networks for graph-constrained house layout g eneration

    Nelson Nauata, Kai-Hung Chang, Chin-Yi Cheng, Greg Mori , and Yasutaka Furukawa. House-gan: Relational generative adversarial networks for graph-constrained house layout g eneration. In European Conference on Computer Vision , pages 162–177. Springer, 2020

    2020

  23. [23]

    House- gan++: Generative adversarial layout refinement network to wards intelligent computational agent for professional ar chi- tects

    Nelson Nauata, Sepidehsadat Hosseini, Kai-Hung Chang, Hang Chu, Chin-Yi Cheng, and Yasutaka Furukawa. House- gan++: Generative adversarial layout refinement network to wards intelligent computational agent for professional ar chi- tects. In Proceedings of the IEEE/CVF Conference on Computer Vision a nd Pattern Recognition , pages 13632–13641, 2021

    2021

  24. [24]

    Actfloor-gan: activity-guided adversarial networks for human-centric floorplan design

    Shidong Wang, Wei Zeng, Xi Chen, Yu Ye, Yu Qiao, and Chi-Wi ng Fu. Actfloor-gan: activity-guided adversarial networks for human-centric floorplan design. IEEE Transactions on Visualization and Computer Graphics , 29(3):1610–1624, 2021

    2021

  25. [25]

    Wallplan: synthesizing floorplans by learning to generate wall graphs

    Jiahui Sun, Wenming Wu, Ligang Liu, Wenjie Min, Gaofeng Z hang, and Liping Zheng. Wallplan: synthesizing floorplans by learning to generate wall graphs. ACM Transactions on Graphics (TOG) , 41(4):1–14, 2022

    2022

  26. [26]

    Housediffusion: Vector floorplan generation via a diffusion model with discrete and continuous denoising

    Safa Shabani, Mohammad Fekri, Mohammad Ali Sadeghi, and Peter Wonka. Housediffusion: Vector floorplan generation via a diffusion model with discrete and continuous denoising . Computer Graphics Forum , 42(7):e14916, 2023

    2023

  27. [27]

    Graph2p ix: A generative model for converting room adjacency relationships into layout images

    ZHEN HAN, XIAOQIAN LI, YE YUAN, and RUDI STOUFFS. Graph2p ix: A generative model for converting room adjacency relationships into layout images. In Proceedings of the 29th International Conference of the Ass ociation for Computer-Aided Architectural Design Research in Asia (CAA DRIA) 2024 , pages 139–148, 2024

    2024

  28. [28]

    Deep learning for automated 3d floor plan gene ration

    Chau Ma Thi. Deep learning for automated 3d floor plan gene ration. VNU JOURNAL OF SCIENCE: COMPUTER SCIENCE AND COMMUNICATION ENGINEERING: Vietnam National U niversity Journal of Science , 2024

    2024

  29. [29]

    Mas kplan: Masked generative layout planning from partial inpu t

    Hang Zhang, Anton Savov, and Benjamin Dillenburger. Mas kplan: Masked generative layout planning from partial inpu t. In Proceedings of the IEEE/CVF Conference on Computer Vision a nd Pattern Recognition , pages 8964–8973, 2024

    2024

  30. [30]

    Cons2plan: Vector floorplan gener- ation from various conditions via a learning framework base d on conditional diffusion models

    Shibo Hong, Xuhong Zhang, Tianyu Du, Sheng Cheng, Xun Wan g, and Jianwei Yin. Cons2plan: Vector floorplan gener- ation from various conditions via a learning framework base d on conditional diffusion models. In Proceedings of the 32nd ACM International Conference on Multimedia , pages 3248–3256, 2024

    2024

  31. [31]

    R esidential floor plans: Multi-conditional automatic generation using diffusion models

    Pengyu Zeng, Wen Gao, Jun Yin, Pengjian Xu, and Shuai Lu. R esidential floor plans: Multi-conditional automatic generation using diffusion models. Automation in Construction , 162:105374, 2024

    2024

  32. [32]

    Gflan: Generative functional layouts

    Mohamed Abouagour and Eleftherios Garyfallidis. Gflan: Generative functional layouts. arXiv preprint arXiv:2512.16275 , 2025

    work page arXiv 2025

  33. [33]

    Turning a graph into a rectangular floor plan

    J Roth, R Hashimshony, and A Wachman. Turning a graph into a rectangular floor plan. Building and Environment , 17(3):163–173, 1982

    1982

  34. [34]

    Depth-first search and linear graph algor ithms

    Robert Tarjan. Depth-first search and linear graph algor ithms. SIAM journal on computing , 1(2):146–160, 1972

    1972

  35. [35]

    Ear-clipping b ased algorithms of generating high-quality polygon tri- angulation

    Gang Mei, John C Tipper, and Nengxiong Xu. Ear-clipping b ased algorithms of generating high-quality polygon tri- angulation. In Proceedings of the 2012 International Conference on Inform ation Technology and Software Engineering: Software Engineering & Digital Media Technology , pages 979–988. Springer, 2012

    2012

  36. [36]

    Existence theorems for floor-plans

    I Rinsma. Existence theorems for floor-plans. Bulletin of the Australian Mathematical Society , 37(3):473–475, 1988

    1988

  37. [37]

    Finding all the elementary circuits of a directed graph

    Donald B Johnson. Finding all the elementary circuits of a directed graph. SIAM Journal on Computing , 4(1):77–84, 1975

    1975

  38. [38]

    Regular edge labeling of 4-connecte d plane graphs and its applications in graph drawing problem s

    Goos Kant and Xin He. Regular edge labeling of 4-connecte d plane graphs and its applications in graph drawing problem s. Theoretical Computer Science , 172(1-2):175–193, 1997

    1997

  39. [39]

    Dfs tree construction: A lgorithms and characterizations: Preliminary version

    Ephraim Korach and Zvi Ostfeld. Dfs tree construction: A lgorithms and characterizations: Preliminary version. In International Workshop on Graph-Theoretic Concepts in Com puter Science , pages 87–106. Springer, 1988

    1988

  40. [40]

    Efficiency of a good but not linear set union algorithm

    Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM (JACM) , 22(2):215–225, 1975

    1975

  41. [41]

    On floor-plan of plane graphs

    Xin He. On floor-plan of plane graphs. SIAM Journal on Computing , 28(6):2150–2167, 1999

    1999

  42. [42]

    Ad dressing adjacency constraints in rectangular floor plans using monte-carlo tree search

    Feng Shi, Ranjith K Soman, Ji Han, and Jennifer K Whyte. Ad dressing adjacency constraints in rectangular floor plans using monte-carlo tree search. Automation in Construction , 115:103187, 2020. 12 Appendix 12.1 Analysis of Performance This section explains the computational performance of our propo sed pipeline and compares it with existing graph- based ...

    2020

  43. [43]

    Algorithm 1 ensures connectivity while respecting non-adjacenc y constraints, producing the graph GC

  44. [44]

    Algorithm 2 augments the graph to achieve bi-connectivity, prod ucing GB

  45. [45]

    Algorithm 3 performs constrained triangulation to obtain GT

  46. [46]

    All four procedures operate directly on a fixed plane embedding of t he graph

    Algorithm 4 removes separating triangles (when required), resu lting in the final graph GF , particularly when each module must correspond to a rectangular region. All four procedures operate directly on a fixed plane embedding of t he graph. At every step, adjacency relations are modified only when necessary and in a clearly defined manner. The pipeline does...

  47. [47]

    The number of added edges satisfies |A|≤ k− 1, and if Algorithm 1 succeeds in merging all components, then |A| = k− 1 (hence the augmentation is minimum in cardinality among all augmentations that connect these k components). Proof. Case 1 : Suppose there exists a set of edges whose insertion into G produces the graph GC , and none of these added edges bel...

    2010

  48. [48]

    Every edge added during the constrained phase satisfies th e non-adjacency constraints, i.e., is not in N

  49. [49]

    If for every articulation point v there exists a set of allowed edges (not in N ) that connects the blocks of GC−{ v}, then the output GB is biconnected. Proof. (1) Connectivity . Algorithm 2 only adds edges to GC (Steps 7–9) and never deletes vertices; adding edges cannot destroy connectivity, hence GB remains connected. (2) Non-adjacency preservation (c...

  50. [50]

    GT is planar and contains GB as a spanning subgraph

  51. [51]

    Every diagonal added by Algorithm 3 respects the non-adja cency constraints (i.e., is not in N )

  52. [52]

    Every bounded face of GT is a triangle; hence GT is a plane triangulated graph. Proof. Algorithm 3 only adds edges, so GB remains a spanning subgraph of the result. By Lemma 4, every acce pted diagonal is non-crossing and lies inside the target face, so planarity is preserved throughout; this proves (1). The same lemma gives (2). For (3), Algorithm 3 iter...

  53. [53]

    GF contains no separating triangles, i.e., ST(GF ) =∅

  54. [54]

    During the constrained replacement stage, every added ed ge (r, d ) satisfies (r, d ) /∈N

  55. [55]

    If the constrained stage cannot reduce m further, the fallback stage (which drops the non-adjacency filter) guar- antees that the algorithm can still reduce m and thus reach ST(G) =∅. Proof. Algorithm 4 begins by computing T = ST(GT ) and m =|T|(Steps 1–4), and then calls RemoveSTEdgeR- emoval to iteratively modify GT until separating triangles disappear, ...