Samenvatting
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
Originele taal-2 | Engels |
---|---|
Titel | Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010) |
Plaats van productie | New York NY |
Uitgeverij | Association for Computing Machinery, Inc |
Pagina's | 429-438 |
ISBN van geprinte versie | 978-1-4503-0016-2 |
Status | Gepubliceerd - 2010 |