### Abstract

Original language | English |
---|---|

Title of host publication | Proceedings 26th Annual ACM Symposium on Computational Geometry (SoCG'10, Snowbird UT, USA, June 13-16, 2010) |

Place of Publication | New York NY |

Publisher | Association for Computing Machinery, Inc |

Pages | 429-438 |

ISBN (Print) | 978-1-4503-0016-2 |

Publication status | Published - 2010 |

### Fingerprint

### Cite this

*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.

}

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 -