Open Access
- 18 October 2023
- journal article
- research article
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (4) , 1429-1455
Abstract
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $${\mathbb {R}}^3$$ . We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $$K_5$$ , $$K_{5,81}$$ , or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $$K_{4,4}$$ , and $$K_{3,5}$$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (Isr. J. Math. 46(1–2), 127–144 (1983)), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in $$\Omega (n\log n)$$ . From the non-realizability of $$K_{5,81}$$ , we obtain that any realizable n-vertex graph has $${\mathcal {O}}(n^{9/5})$$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.
Keywords
All Related Versions
Funding Information
- Julius-Maximilians-Universität Würzburg
This publication has 43 references indexed in Scilit:
- Extending Steinitz’s Theorem to Upward Star-Shaped Polyhedra and Spherical PolyhedraAlgorithmica, 2011
- Optimal Polygonal Representation of Planar GraphsAlgorithmica, 2011
- Polyhedral Surfaces of High Genus2008
- Facility Location on a Polyhedral SurfaceDiscrete & Computational Geometry, 2003
- Contact graphs of line segments are NP-completeDiscrete Mathematics, 2001
- Unit disk graph recognition is NP-hardComputational Geometry, 1998
- Computational geometry and computer graphicsProceedings of the IEEE, 1992
- Visibility problems for polyhedral terrainsJournal of Symbolic Computation, 1989
- On Steinitz's theorem concerning convex 3-polytopes and on some properties of planar graphs1969
- Über das Problem der Nachbargebiete im RaumMonatshefte für Mathematik, 1905