Embedding the dual complex of hyper-rectangular partitions

DOI10.20382/JOCG.V4I1A2MaRDI QIDQ2968095zbMATH OpenOpenAlexFDO

Authors Michael Kerber

Publication date 9 March 2017

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

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)

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.

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

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)