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 K₅ and every nonplanar 3-tree does not admit a representation with convex polygons. On the other hand, K_4, 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.

Journal Article (peer-reviewed)

Conference Proceedings (peer-reviewed)

Workshop or Poster (weakly reviewed)

Archived Publication (not reviewed)

back to list