Steinitz theorems for orthogonal polyhedra

D. Eppstein, E. Mumford

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

20 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

Polyhedron
Theorem
Vertex of a graph
Graph in graph theory
Convex polyhedron
Connected Components
Isometric
Bipartite Graph
Planar graph
Perpendicular
Analogy
Efficient Algorithms
Projection
Topology
Three-dimensional
Line

Cite this

Eppstein, D., & Mumford, E. (2010). Steinitz theorems for orthogonal polyhedra. In Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010) (pp. 429-438). New York NY: Association for Computing Machinery, Inc.
Eppstein, D. ; Mumford, E. / Steinitz theorems for orthogonal polyhedra. Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010). New York NY : Association for Computing Machinery, Inc, 2010. pp. 429-438
@inproceedings{a71f9c22e2f54e4ca2ef78862c387db0,
title = "Steinitz theorems for orthogonal polyhedra",
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",
author = "D. Eppstein and E. Mumford",
year = "2010",
language = "English",
isbn = "978-1-4503-0016-2",
pages = "429--438",
booktitle = "Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010)",
publisher = "Association for Computing Machinery, Inc",
address = "United States",

}

Eppstein, D & Mumford, E 2010, Steinitz theorems for orthogonal polyhedra. in Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010). Association for Computing Machinery, Inc, New York NY, pp. 429-438.

Steinitz theorems for orthogonal polyhedra. / Eppstein, D.; Mumford, E.

Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010). New York NY : Association for Computing Machinery, Inc, 2010. p. 429-438.

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

TY - GEN

T1 - Steinitz theorems for orthogonal polyhedra

AU - Eppstein, D.

AU - Mumford, E.

PY - 2010

Y1 - 2010

N2 - 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

AB - 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

UR - http://doi.acm.org/10.1145/1810959.1811030

M3 - Conference contribution

SN - 978-1-4503-0016-2

SP - 429

EP - 438

BT - Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010)

PB - Association for Computing Machinery, Inc

CY - New York NY

ER -

Eppstein D, Mumford E. Steinitz theorems for orthogonal polyhedra. In Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010). New York NY: Association for Computing Machinery, Inc. 2010. p. 429-438