KIT | KIT-Bibliothek | Impressum | Datenschutz

Plattenbauten: Touching Rectangles in Space

Felsner, Stefan; Knauer, Kolja; Ueckerdt, Torsten

Abstract:
Planar bipartite graphs can be represented as touching graphs of horizontal and vertical segments in ℝ2. We study a generalization in space, namely, touching graphs of axis-aligned rectangles in ℝ3. We prove that planar 3-colorable graphs can be represented as touching graphs of axis-aligned rectangles in ℝ3. The result implies a characterization of corner polytopes previously obtained by Eppstein and Mumford. A by-product of our proof is a distributive lattice structure on the set of orthogonal surfaces with given skeleton.
Moreover, we study the subclass of strong representations, i.e., families of axis-aligned rectangles in ℝ3 in general position such that all regions bounded by the rectangles are boxes. We show that the resulting graphs correspond to octahedrations of an octahedron. This generalizes the correspondence between planar quadrangulations and families of horizontal and vertical segments in ℝ2 with the property that all regions are rectangles.



Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsdatum 15.07.2020
Sprache Englisch
Identifikator KITopen-ID: 1000126331
Schlagwörter Touching graphs, contact graphs, boxicity, planar graphs
Nachgewiesen in arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page