Embedding the dual complex of hyper-rectangular partitions

DOI10.20382/JOCG.V4I1A2zbMATH Open1408.52033arXiv1207.3202OpenAlexW1934609795MaRDI QIDQ2968095FDOQ2968095

Authors: Michael Kerber 

Publication date: 9 March 2017

Abstract: A rectangular partition is the partition of an (axis-aligned) rectangle into interior-disjoint rectangles. We ask whether a rectangular partition permits a "nice" drawing of its dual, that is, a straight-line embedding of it such that each dual vertex is placed into the rectangle that it represents. We show that deciding whether such a drawing exists is NP-complete. Moreover, we consider the drawing where a vertex is placed in the center of the represented rectangle and consider sufficient conditions for this drawing to be nice. This question is studied both in the plane and for the higher-dimensional generalization of rectangular partitions.

Full work available at URL: https://arxiv.org/abs/1207.3202

Recommendations

• Rectangular duals of planar graphs
• Drawing the planar dual
• Orientation-Constrained Rectangular Layouts
• Rectangular dualization and rectangular dissections
• scientific article; zbMATH DE number 1974124

zbMATH Keywords

embeddingdual complexrectangular partitions

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Cited In (2)

• On stable embeddability of partitions
• Partitioned Drawings

This page was built for publication: Embedding the dual complex of hyper-rectangular partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968095)