×

On representing graphs by touching cuboids. (English) Zbl 1377.68166

Didimo, Walter (ed.) et al., Graph drawing. 20th international symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-36762-5/pbk). Lecture Notes in Computer Science 7704, 187-198 (2013).
Summary: We consider contact representations of graphs where vertices are represented by cuboids, i.e. interior-disjoint axis-aligned boxes in 3D space. Edges are represented by a proper contact between the cuboids representing their endvertices. Two cuboids make a proper contact if they intersect and their intersection is a non-zero area rectangle contained in the boundary of both. We study representations where all cuboids are unit cubes, where they are cubes of different sizes, and where they are axis-aligned 3D boxes. We prove that it is NP-complete to decide whether a graph admits a proper contact representation by unit cubes. We also describe algorithms that compute proper contact representations of varying size cubes for relevant graph families. Finally, we give two new simple proofs of a theorem by Thomassen stating that all planar graphs have a proper contact representation by touching cuboids.
For the entire collection see [Zbl 1258.68009].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05B50 Polyominoes
05C62 Graph representations (geometric and intersection representations, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI