Many vision systems first detect pieces (wall segments, corners, lines) and then assemble them into a structure. When the detector misses or hallucinates a piece, the assembled structure breaks, and nothing downstream can fix it. Floorplans show this clearly. Walls should divide the building's footprint into closed rooms, with the building exterior as one fixed outer region. A single missing wall either merges two rooms or leaves a "leaky" polygon that does not close. We propose to treat this repair problem as constrained graph completion. The confident detections become a partial drawing that cannot change, anchored to the building exterior. The detector's low-confidence and hypothesized walls become optional edges. The decoder then picks the highest-scoring set of optional walls whose combined drawing can still be completed into a valid planar subdivision.
What is new is how the search stays tractable and interpretable. When a candidate set is infeasible, a known certifying algorithm for partially embedded planarity returns a minimal obstruction: a small witness pattern showing why no completion exists. That witness becomes a cut, a constraint telling the optimizer that at least one specific wall in it must go. The SPQR tree, a standard decomposition of a graph into series, parallel and rigid pieces, splits the problem at two-vertex separations into near-independent subproblems. The same obstructions also say which region of the scan the detector got wrong. That gives a structural signal of where upstream errors originated, which no current floorplan model produces.
Core Claim
Selecting a crossing-free set of wall segments by checking pairwise crossings is easy. Guaranteeing that the selected set closes every room and agrees with the building exterior is a global property that pairwise checks miss. Exact optimization over it is NP-hard: Testing Planarity of Partially Embedded Graphs shows that minimizing rerouted edges in partial-embedding extension is NP-hard. Our claim is that conflict-driven search, with obstruction certificates as cuts, makes this global repair practical at floorplan scale. We further claim it improves topological validity and corner accuracy over local geometric closure exactly where detectors fail most, namely under occlusion and cross-dataset shift. The claim is falsifiable. If a geometric integer program with only pairwise crossing and vertex-degree constraints matches it, the topological machinery is not earning its keep, and we will report that.
Background and Positioning
Three graph-drawing results supply the method. Testing Planarity of Partially Embedded Graphs decides in linear time whether a graph with a pre-drawn subgraph can be completed planarly. It does this by propagating the fixed subgraph's constraints through SPQR trees, which restrict which parallel pieces may be reordered and which rigid pieces may be mirrored. The algorithm only answers yes or no, assumes a crisp input graph, and says nothing about repair. A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs characterizes every failure. Each non-extendable instance contains one of 22 exceptional minimal obstructions or an "alternating chain." The authors also give a polynomial-time algorithm that outputs either a completion or such a certificate. We reuse this certifying algorithm as the infeasibility oracle. It was designed for exact inputs, and we use it on noisy ones. Planar Embeddings with Small and Uniform Faces runs dynamic programs over SPQR trees to control face sizes and uses Euler's formula to bound the outer face. It supplies the template for optimizing room-shape priors inside the decomposition.
One more result shapes our design, specifically the choice of what to anchor. The Crossing Number of Semi-Pair-Shellable Drawings of Complete Graphs relaxes the classical requirement of a globally fixed reference face. It lets the reference face hop to an adjacent face. In our setting the reference face is the detected building exterior, and that exterior is itself a detector output. Anchoring a wrong exterior rigidly would push its error into every room. We therefore let the exterior anchor be revised by local hops when a certificate implicates it. This is a loose analogy to their construction, not a reuse of their proof. The paradox of rigidity points the same way. Fixing rotation systems makes some recognition problems harder (fan-planar recognition), and anchoring vertex positions makes crossing-free drawing NP-hard (Anchored Graph Drawing). Both results warn that over-anchoring noisy detections can make every completion infeasible. We therefore anchor only the combinatorial order of high-confidence walls, not their coordinates.
Several results motivate the work by showing the cascade in practice. RoomFormer documents room polygons collapsing when an occluded corner is missed. CAGE moves to edge-centric wall prediction and closes rooms with a deterministic pairwise line-intersection module. It is our host detector and our main competitor. Its closure step is local and has no notion of whether the full set of walls forms a consistent subdivision of the exterior. TopoMLP shows that in driving topology, detection quality dominates. That is a constraint on our ambitions: structure cannot recover what the detector never proposed. Our candidate pool must therefore include sub-threshold detections, not only accepted ones.
We deliberately exclude OpenLane-V2. Lane graphs cross at intersections and overpasses, so planarity is the wrong prior there.
Research Program
The detector is CAGE run from its official codebase. We split its wall queries by confidence. Walls above a high threshold, together with their cyclic order at shared corners, form the fixed partial drawing $H$. The detected exterior boundary, or a convex-hull fallback when that boundary is incomplete, serves as the reference face $R$. Walls between the low and high thresholds form the candidate set $C$. So do hypothesized completions: extending a dangling wall to its nearest wall, and joining endpoint pairs within a distance tolerance. Each candidate $e$ gets a score $w_e$, its detector log-odds. The decoder solves
$$\max_{S \subseteq C} \sum_{e \in S} w_e \quad \text{subject to } (H \cup S, R) \text{ being extendable, biconnected, with } R \text{ as its outer face},$$
where biconnectivity encodes "every wall separates two different regions," which is the topological form of watertightness.
We solve this as an integer program with lazy constraints. Each incumbent $S$ goes to the certifying algorithm of Jelínek, Kratochvíl and Rutter. If it returns an obstruction whose free edges are $O \subseteq S$, we add the cut $\sum_{e \in O} x_e \le |O|-1$, where $x_e$ indicates selection of $e$. When the obstruction contains no free edge, the anchors alone are contradictory, so we downgrade the implicated anchors, including $R$, to candidates. That step is the reference-face hop. Biconnectivity failures yield cut-vertex cuts in the same way.
Before search, we compute the SPQR tree of $H$ together with the high-score candidates. We optimize separately within the pieces at each two-vertex separation and combine them with a dynamic program in the style of Da Lozzo et al.. The final walls go back through CAGE's intersection module to recover straight-line geometry.
One gap is a known risk and is measured, not assumed away. Topological extendability is necessary but not sufficient for a straight-wall drawing. We will report how often a topologically valid output fails geometric realization.
Beyond accuracy, every obstruction is a localized explanation of a detector error. We will test whether lowering the detector threshold only inside certified regions recovers missed walls more efficiently than lowering it globally.
Baselines
The naive reference point is CAGE's own output, with its pairwise intersection post-processing, at its default threshold. It reports 99.1% room F1, 91.7% corner F1 and 89.3% angle F1 on Structured3D, and 85.6% room IoU on SceneCAD when trained on Structured3D (CAGE). This is also the strongest existing method. Beating it means improving corner or angle F1 or SceneCAD room IoU without losing room F1, given that room F1 leaves less than one point of headroom. We also report RoomFormer as a corner-centric reference: 97.3% room F1 on Structured3D and 74.0 room IoU on SceneCAD. Every repair method starts from the same trained CAGE checkpoint, uses the same candidate pool, and gets the same per-scene solver time limit. Thresholds are tuned on the same validation split with the same number of trials.
The strongest structural competitor is one we construct ourselves. It is a geometric integer program that maximizes the same score subject to pairwise segment non-crossing and a minimum vertex degree of two. It is the obvious cheap way to get crossing-free, non-dangling walls. If it ties our decoder, the global topological constraints are unnecessary.
Three ablations isolate the ingredients. The first replaces obstruction cuts with generic "not this exact set" cuts, which isolates the value of minimal certificates for convergence speed. The second freezes the reference face instead of allowing hops, which isolates the cost of rigidly anchoring a possibly wrong exterior. The third runs the solver on the whole graph without SPQR factorization, which measures runtime only.
Why not just…?
Why not just upgrade the detector? This is a real effect. In TopoMLP, adding YOLOv8 proposals raised traffic-element detection from 50.0 to 53.3 and improved downstream topology with no change to the reasoner. We test it directly by running CAGE with its Swin Transformer backbone instead of ResNet-50 and applying our decoder on top of both. The proposal survives only if the gain from repair persists on the stronger backbone. If the gain vanishes there, repair is a substitute for capacity rather than a complement, and we will say so.
Why not just predict the whole structure end to end? Single-stage set prediction removes region-proposal bottlenecks (Pixels to Graphs by Associative Embedding). It does not, however, guarantee closed rooms. RoomFormer, which is end to end, still loses rooms under occlusion, and CAGE still needs a deterministic closure step. We do not compete with end-to-end training. We replace that final closure step and compare against it directly.
Why not just use geometric post-processing, snapping and intersections, or the pairwise integer program? This is the most serious threat. CAGE's local closure already achieves the numbers above in 0.01 seconds. Our argument is that pairwise checks cannot see global failures. Two walls that do not cross can still leave a bridge, or split the exterior inconsistently, and noisy coordinates create spurious crossings and missed junctions that a combinatorial anchor tolerates. That argument is untested. The pairwise integer program baseline under controlled localization noise settles it. If it matches us across noise levels, we drop the topological layer and report a negative result.
Proposed Experiments
We evaluate on Structured3D and on SceneCAD cross-dataset transfer, using room, corner and angle F1, room IoU, and a topological validity rate: the fraction of outputs that are biconnected planar subdivisions whose outer face matches ground truth. To probe the regime where cascading errors dominate, we add two controlled stresses to Structured3D inputs. One masks rectangular regions of the density map to simulate occlusion. The other jitters predicted endpoints to simulate localization noise. The decisive check is the gap between our decoder and the pairwise integer program as both stresses increase. The topological approach predicts that this gap widens with occlusion and noise. A flat or negative gap refutes the core claim.
The secondary checks cover the remaining claims. First, the fixed-versus-revisable exterior ablation should help mainly on scenes where the exterior detection is wrong. Second, threshold lowering targeted by certificates should recover a given number of missed walls with fewer false positives than global lowering. Third, the geometric realization failure rate should stay low enough that the topological guarantee means something in practice.
As a small transfer probe, we will apply the same decoder to diagram graphs on PGPS9K. There the bounding face plays the reference role, and the 66.6% completion rate of Geo-Graph is a ceiling that the paper attributes to parser omissions. That probe is exploratory, and we make no claim about it in advance.
References
- Testing Planarity of Partially Embedded Graphs
- A kuratowski-type theorem for planarity of partially embedded graphs
- Planar Embeddings with Small and Uniform Faces
- The Crossing Number of Semi-Pair-Shellable Drawings of Complete Graphs
- On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
- Anchored Drawings of Planar Graphs
- Connecting the Dots: Floorplan Reconstruction Using Two-Level Queries
- CAGE: Continuity-Aware edGE Network Unlocks Robust Floorplan Reconstruction
- TopoMLP: A Simple yet Strong Pipeline for Driving Topology Reasoning
- Pixels to Graphs by Associative Embedding
- Encode Geometric Diagram as Geo-Graph in Geometry Problem Solving