Rectangular duals of planar graphs
Krzysztof Koźmiński, E. Kinnen · Networks · 1985
Abstract Let one face of a cube be dissected into rectangles, no 4 of which meet at a single point. The dual graph of this configuration is a 4‐connected triangulated plane graph. This paper shows that any 4‐connected plane triangulation with at least 6 vertices and at least one vertex of degree 4 is dual to a cube with one face dissected into rectangles. The proof of this result contains an implicit algorithm for obtaining such a dissection. The paper also discusses a related problem: Given a graph G with all faces triangular except the outer face, does there exist a dissection of a rectangle into rectangles for which G describes the adjacency relations among the rectangles?