Plattenbauten: Touching Rectangles in Space

DOI10.1007/978-3-030-60440-0_13MaRDI QIDQ6345169arXivFDO

Authors Stefan Felsner, Kolja Knauer, Torsten Ueckerdt

Publication date 15 July 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-60440-0_13

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.CGcs.DMmath.CO

Abstract: Planar bipartite graphs can be represented as touching graphs of horizontal and vertical segments in $mathbb{R}^2$. We study a generalization in space, namely, touching graphs of axis-aligned rectangles in $mathbb{R}^3$. We prove that planar $3$-colorable graphs can be represented as touching graphs of axis-aligned rectangles in $mathbb{R}^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 $mathbb{R}^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 $mathbb{R}^2$ with the property that all regions are rectangles.

This page was built for publication: Plattenbauten: Touching Rectangles in Space

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