Steinitz theorems for orthogonal polyhedra

D. Eppstein, E. Mumford

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

23 Citaten (Scopus)
2 Downloads (Pure)

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-2Engels
TitelProceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010)
Plaats van productieNew York NY
UitgeverijAssociation for Computing Machinery, Inc
Pagina's429-438
ISBN van geprinte versie978-1-4503-0016-2
StatusGepubliceerd - 2010

Vingerafdruk

Duik in de onderzoeksthema's van 'Steinitz theorems for orthogonal polyhedra'. Samen vormen ze een unieke vingerafdruk.

Citeer dit