### Steinitz theorems for simple 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 find graph-theoretic characterizations of three classes of simple orthogonal polyhedra:*corner polyhedra*, which can be drawn by isometric projection in the plane with only one hidden vertex,*xyz polyhedra*, in which each axis-parallel line through a vertex contains exactly one other vertex, and arbitrary simple orthogonal polyhedra. In particular, the graphs of*xyz*polyhedra are exactly the bipartite cubic polyhedral graphs, and every bipartite cubic polyhedral graph with a 4-connected dual graph is the graph of a corner polyhedron. Based on our characterizations we find efficient algorithms for constructing orthogonal polyhedra from their graphs.#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v5i1a10

ISSN: 1920-180X