caa a22 4500 445805404 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-011-9570-x doi (NATIONALLICENCE)springer-10.1007/s00453-011-9570-x Extending Steinitz's Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra [Elektronische Daten] [Seok-Hee Hong, Hiroshi Nagamochi] In1922, Steinitz's theorem gave a complete characterization of the topological structure of the vertices, edges, and faces of convex polyhedra as triconnected planar graphs. In this paper, we generalize Steinitz's theorem to non-convex polyhedra. More specifically, we introduce a new class of polyhedra, wider than convex polyhedra, called upward star-shaped polyhedra and spherical polyhedra, and present graph-theoretic characterization for both polyhedra. Upward star-shaped polyhedra are polyhedra where each face is star-shaped, all faces except the bottom face are visible from a view point, and any two faces sharing two vertices are non-coplanar. Spherical polyhedra are non-singular, non-coplanar polyhedra with no holes. We first present a graph-theoretic characterization of upward star-shaped polyhedra, i.e., characterization of upward star-shaped polyhedral graphs, which are the vertex-edge graphs (or 1-skeleton) of the upward star-shaped polyhedra. Roughly speaking, they correspond to biconnected planar graphs with special conditions. The proof of the characterization leads to an algorithm that constructs an upward star-shaped polyhedron with n vertices in O(n 1.5) time. Moreover, one can test whether a given plane graph is an upward star-shaped polyhedral graph in linear time. We then present a graph-theoretic characterization of spherical polyhedra for planar cubic graphs, and planar graphs with maximum face size4. We also formally define the Polyhedra Realizability Problem, and discuss its reducibility. Our result is the first graph-theoretic characterization of non-convex polyhedra, which solves an open problem posed by Grünbaum(Discrete Math. 307(3-5), 445-463,2007), and a generalization of Steinitz's theorem(Polyeder und Raumeinteilungen, 1922), which characterized convex polyhedra as triconnected planar graphs. Springer Science+Business Media, LLC, 2011 Graph drawing nationallicence Steinitz's theorem nationallicence Convex drawing nationallicence Planar graphs nationallicence Biconnected graphs nationallicence Triconnected graphs nationallicence Polyhedra nationallicence Polytopes nationallicence Convex polytopes nationallicence Non-convex polytopes nationallicence Polyhedral graphs nationallicence Upward star-shaped polyhedra nationallicence Spherical polyhedra nationallicence Hong Seok-Hee School of Information Technologies, University of Sydney, Sydney, Australia aut Nagamochi Hiroshi Graduate School of Informatics, Kyoto University, Kyoto, Japan aut Algorithmica Springer-Verlag 61/4(2011-12-01), 1022-1076 0178-4617 61:4<1022 2011 61 453 https://doi.org/10.1007/s00453-011-9570-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-011-9570-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hong Seok-Hee School of Information Technologies, University of Sydney, Sydney, Australia aut NATIONALLICENCE 700 1- Nagamochi Hiroshi Graduate School of Informatics, Kyoto University, Kyoto, Japan aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 1022-1076 0178-4617 61:4<1022 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer