Side-Contact Representations with Convex Polygons in 3D: New Results for Complete Bipartite Graphs

2023/08/01 by Schulz, André
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2308.00380

Abstract

A polyhedral surface~C in ℝ³ with convex polygons as faces is a side-contact representation of a graph~G if there is a bijection between the vertices of G and the faces of~C such that the polygons of adjacent vertices are exactly the polygons sharing an entire common side in~C. We show that K_3,8 has a side-contact representation but K_3,250 has not. The latter result implies that the number of edges of a graph with side-contact representation and n vertices is bounded by O(n^5/3).

Related

• Optimal Polygonal Representation of Planar Graphs
• Regular Polygon Surfaces
• Axis-Aligned Square Contact Representations
• Contact Representations of Graphs in 3D
• The intersection graph of the disks with diameters the sides of a convex n-gon