Steinitz theorems for orthogonal polyhedra

D. Eppstein, E. Mumford

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

21 Citations (Scopus)
2 Downloads (Pure)

Abstract

We define a simple orthogonal polyhedron to be a three-dimensional polyhedron with the topology of a sphere in which three mutually-perpendicular edges meet at each vertex. By analogy to Steinitz's theorem characterizing the graphs of convex polyhedra, we characterize the graphs of simple orthogonal polyhedra: they are exactly the 3-regular bipartite planar graphs in which the removal of any two vertices produces at most two connected components. We also characterize two subclasses of these polyhedra: corner polyhedra, which can be drawn by isometric projection in the plane with only one hidden vertex, and xyz polyhedra, in which each axis-parallel line through a vertex contains exactly one other vertex. Based on our characterizations we find efficient algorithms for constructing orthogonal polyhedra from their graphs
Original languageEnglish
Title of host publicationProceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages429-438
ISBN (Print)978-1-4503-0016-2
Publication statusPublished - 2010

Fingerprint Dive into the research topics of 'Steinitz theorems for orthogonal polyhedra'. Together they form a unique fingerprint.

Cite this