Adjacency Graphs of Polyhedral Surfaces

A graph has a side-contact representation with polygons if its vertices can be represented by interior-disjoint polygons such that two polygons share a common side if and only if the corresponding vertices are adjacent. In this work we study representations in 3D. We show that every graph has a side-contact representation with polygons in 3D, while this is not the case if we additionally require that the polygons are convex: we show that every supergraph of K5 and every nonplanar 3-tree does not admit a representation with convex polygons. On the other hand, K4, 4 admits such a representation, and so does every graph obtained from a complete graph by subdividing each edge once. Finally, we construct an unbounded family of graphs with average vertex degree 12 − o(1) that admit side-contact representations with convex polygons in 3D. Hence, such graphs can be considerably denser than planar graphs.

keywords: Computational Geometry, Graph Drawing, Graphs Theory, Higher Dimensions

Conference Proceedings (peer-reviewed)

Alexander Wolff, André Schulz, Birgit Vogtenhuber, Boris Klemz, Elena Arseneva, Linda Kleist, Maarten Löffler
Adjacency Graphs of Polyhedral Surfaces
Proc. 37th International Symposium on Computational Geometry
11:1–11:17, 2021

Workshop or Poster (weakly reviewed)

Alexander Wolff, André Schulz, Birgit Vogtenhuber, Boris Klemz, Elena Arseneva, Linda Kleist, Maarten Löffler
Representing Graphs by Polygons with Side Contacts in 3D
Proc. 36st European Workshop on Computational Geometry
53:1–8, 2020

Archived Publication (not reviewed)

Alexander Wolff, André Schulz, Birgit Vogtenhuber, Boris Klemz, Elena Arseneva, Linda Kleist, Maarten Löffler
Adjacency Graphs of Polyhedral Surfaces
2103.09803, 2021
http://arXiv.org/abs/2103.09803

back to list