research-article

Steinitz theorems for orthogonal polyhedra

Authors:

David Eppstein,

Elena MumfordAuthors Info & Claims

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

Pages 429 - 438

https://doi.org/10.1145/1810959.1811030

Published: 13 June 2010 Publication History

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

References

[1]

A. A. Andersson and M. Thorup. Tight(er) worst-case bounds on dynamic searching and priority queues. Proc. 32nd ACM Symp. Theory of Computing (STOC 2000), pp. 335--342, 2000.

Digital Library

[2]

S. Aziza and T. Biedl. Hexagonal grid drawings: algorithms and lower bounds. Proc. 12th Int. Symp. Graph Drawing (GD 2004), 3383 edition, pp. 18--24. Springer-Verlag, Lecture Notes in Computer Science, 2005.

Digital Library

[3]

M. L. Balinski. On the graph structure of convex polyhedra in n-space. Pacific J. Math. 11(2):431--434, 1961, http://projecteuclid.org/euclid.pjm/1103037323.

[4]

D. W. Barnette. Conjecture 5. Recent Progress in Combinatorics, p. 343. Academic Press, 1969.

[5]

V. Batagelj. An improved inductive definition of two restricted classes of triangulations of the plane. Combinatorics and Graph Theory, Warsaw, 1987, 25 edition, pp. 11--18. PWN, Banach Center Publ., 1989.

[6]

S. Bhatt and S. Cosmodakis. The complexity of minimizing wire lengths in VLSI layouts. Inform. Proc. Lett. 25:263--267, 1987.

Digital Library

[7]

T. Biedl, E. Demaine, M. Demaine, A. Lubiw, M. Overmars, J. O'Rourke, S. Robbins, and S. Whitesides. Unfolding some classes of orthogonal polyhedra. Proc. 10th Canadian Conference on Computational Geometry (CCCG'98), 1998, http://erikdemaine.org/papers/CCCG98b/.

[8]

T. Biedl and B. Genc. When can a graph form an orthogonal polyhedron? Proc. 16th Canadian Conf. Computational Geometry (CCCG 2004), pp. 53--56, 2004, http://www.cccg.ca/proceedings/2004/15.pdf.

[9]

T. Biedl and B. Genc. Cauchy's theorem for orthogonal polyhedra of genus 0. Proc. 17th European Symp. Algorithms (ESA 2009), 5757 edition, pp. 71--83. Springer-Verlag, Lecture Notes in Computer Science, 2009.

[10]

J. Bokowski and A. Guedes de Oliveira. On the generation of oriented matroids. Discrete and Computational Geometry 24(2-3):197--208, 2000.

[11]

G. Brinkmann and B. D. McKay. Fast generation of planar graphs. Communications in Mathematical and in Computer Chemistry 58(2):323--357, 2007, http://cs.anu.edu.au/people/bdm/papers/plantri-full.pdf.

[12]

M. Bruls, K. Huizing, and J. J. van Wijk. Squarified treemaps. Data Visualization 2000: Proc. Joint Eurographics and IEEE TCVG Symp. on Visualization, pp. 33--42. Springer-Verlag, 2000, http://www.win.tue.nl/~vanwijk/stm.pdf.

[13]

A. L. Cauchy. Sur les polygones et polyèdres. J. École Polytechnique 19:87--98, 1813.

[14]

N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1):210--223, 1985.

Digital Library

[15]

M. Chrobak and D. Eppstein. Planar orientations with low out-degree and compaction of adjacency matrices. Theoretical Computer Science 86(2):243--266, September 1991.

Digital Library

[16]

H. Cohn, M. Larsen, and J. Propp. The shape of a typical boxed plane partition. New York J. Math. 4:137--165, 1998, http://arxiv.org/abs/math.CO/9801059arXiv:math.CO/9801059, http://nyjm.albany.edu:8000/j/1998/4_137.html.

[17]

R. Connelly. A counterexample to the rigidity conjecture for polyhedra. Pub. Math. de l'IHÉS 47:333--338, 1977.

[18]

R. Connelly, I. Sabitov, and A. Walz. The bellows conjecture. Beitrage Algebra Geom. 38:1--10, 1997, http://www.emis.de/journals/BAG/vol.38/no.1/1.html.

[19]

A. Császár. A polyhedron without diagonals. Acta Sci. Math. Szeged 13:140--142, 1949.

[20]

G. Di Battista and R. Tamassia. Incremental planarity testing. Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), pp. 436--441, 1989.

Digital Library

[21]

G. Di Battista and R. Tamassia. On-line graph algorithms with SPQR-trees. Proc. 17th Internat. Colloq. Automata, Languages and Programming (ICALP 1990), 443 edition, pp. 598--611. Springer-Verlag, Lecture Notes in Computer Science, 1990.

Digital Library

[22]

M. B. Dillencourt and W. D. Smith. Graph-theoretical conditions for inscribability and Delaunay realizability. Discrete Math. 161(1-3):63--77, 1996.

Digital Library

[23]

M. Donoso and J. O'Rourke. Nonorthogonal polyhedra built from rectangles. Proc. 14th Canadian Conference on Computational Geometry (CCCG'98), 2002, http://arxiv.org/abs/cs/0110059arXiv:cs/0110059.

[24]

V. Dujmović, D. Eppstein, M. Suderman, and D. R. Wood. Drawings of planar graphs with few slopes and segments. Computational Geometry Theory & Applications 38(3):194--212, 2007. arXiv:math/0606450.

Digital Library

[25]

V. Dujmović, M. Suderman, and D. R. Wood. Graph drawings with few slopes. Computational Geometry Theory & Applications 38(3):181--193, 2007. arXiv:math/0606446.

Digital Library

[26]

C. F. Earl and L. J. March. Architectural applications of graph theory. Applications of Graph Theory, pp. 327--355. Academic Press, 1979.

[27]

D. Eppstein. The lattice dimension of a graph. Eur. J. Combinatorics 26(5):585--592, July 2005. arXiv:cs.DS/0402028.

Digital Library

[28]

D. Eppstein. Cubic partial cubes from simplicial arrangements. Electronic J. Combinatorics 13(1, R79):1--14, September 2006, arXiv:math.CO/0510263, http://www.combinatorics.org/Volume_13/Abstracts/v13i1r79.html.

[29]

D. Eppstein. Isometric diamond subgraphs. Proc. 16th Int. Symp. Graph Drawing (GD 2008), 5417 edition, pp. 384--389. Springer-Verlag, Lecture Notes in Computer Science, 2008. arXiv:0807.2218.

Digital Library

[30]

D. Eppstein. The topology of bendless three-dimensional orthogonal graph drawing. Proc. 16th Int. Symp. Graph Drawing (GD 2008), 5417 edition, pp. 78--89. Springer-Verlag, Lecture Notes in Computer Science, 2008. arXiv:0709.4087.

Digital Library

[31]

D. Eppstein and E. Mumford. Orientation-constrained rectangular layouts. Proc. Algorithms and Data Structures Symposium (WADS 2009), 5664 edition, pp. 266--277. Springer-Verlag, Lecture Notes in Computer Science, 2009, arXiv:0904.4312.

Digital Library

[32]

D. Eppstein and E. Mumford. Steinitz Theorems for Orthogonal Polyhedra, arXiv:arXiv:0912.0537v1. Electronic preprint, 2010.

[33]

D. Eppstein, E. Mumford, B. Speckmann, and K. A. B. Verbeek. Area-universal rectangular layouts. Proc. 25th ACM Symp. Comp. Geom., pp. 267--276, 2009. arXiv:0901.3924.

Digital Library

[34]

S. Felsner and F. Zickfeld. Schnyder woods and orthogonal surfaces. Discrete and Computational Geometry 40(1):103--126, 2008.

Digital Library

[35]

É. Fusy. Transversal structures on triangulations, with application to straight-line drawing. Proc. 13th Int. Symp. Graph Drawing (GD 2005), 3843 edition, pp. 177--188. Springer-Verlag, Lecture Notes in Computer Science, 2006. http://algo.inria.fr/fusy/Articles/FusyGraphDrawing.pdf.

Digital Library

[36]

É. Fusy. Transversal structures on triangulations: A combinatorial study and straight-line drawings. Discrete Mathematics 309(7):1870--1894, 2009. arXiv:math/0602163.

Digital Library

[37]

B. Grünbaum. Convex Polytopes. Graduate Texts in Mathematics. Springer-Verlag, Berlin, Heidelberg, and New York, 2nd edition, 2003.

[38]

C. Gutwenger and P. Mutzel. A linear time implementation of SPQR-trees. Proc. 8th Int. Symp. Graph Drawing (GD 2000), 1984 edition, pp. 77--90. Springer-Verlag, Lecture Notes in Computer Science, 2001.

Digital Library

[39]

P. J. Heawood. On the four-colour map theorem. Quarterly J. Pure Appl. Math. 29:270--285, 1898.

[40]

C. D. Hodgson, I. Rivin, and W. D. Smith. A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere. Bull. Amer. Math. Soc. 27:246--251, 1992.

[41]

S.-H. Hong and H. Nagamochi. Extending Steinitz' Theorem to Non-convex Polyhedra. Tech. Rep. 2008-012, Department of Applied Mathematics & Physics, Kyoto University, 2008, http://www.amp.i.kyoto-u.ac.jp/tecrep/abst/2008/2008-012.html.

[42]

J. Hopcroft and R. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput. 2(3):135--158, 1973.

Digital Library

[43]

J. Hopcroft and R. Tarjan. Efficient Planarity Testing. J. ACM 21(4):549--568, 1974.

Digital Library

[44]

D. A. Huffman. Impossible objects as nonsense sentences. Machine Intelligence 6, pp. 295--323. Edinburgh University Press, 1971.

[45]

G. Kant. Hexagonal grid drawings. Proc. Int. Worksh. Graph-Theoretic Concepts in Computer Science, 657 edition, pp. 263--276. Springer-Verlag, Lecture Notes in Computer Science, 1993.

Digital Library

[46]

G. Kant and X. He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science 172(1-2):175--193, 1997.

Digital Library

[47]

B. Keszegh, J. Pach, D. Pálvölgyi, and G. Tóth. Drawing cubic graphs with at most five slopes. Computational Geometry Theory & Applications 40(2):138--147, 2008.

Digital Library

[48]

L. M. Kirousis and C. H. Papadimitriou. The complexity of recognizing polyhedral scenes. Journal of Computer and System Sciences 37(1):14--38, 1988. http://lca.ceid.upatras.gr/~kirousis/publications/j29.pdf.

Digital Library

[49]

K. Kozminski and E. Kinnen. Rectangular duals of planar graphs. Networks 5(2):145--157, 1985.

[50]

M. Löffler and E. Mumford. Connected rectilinear graphs on point sets. Proc. 16th Int. Symp. Graph Drawing (GD 2008), 5417 edition, pp. 313--318. Springer-Verlag, Lecture Notes in Computer Science, 2008. http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-028.pdf.

[51]

S. Mac Lane. A structural characterization of planar combinatorial graphs. Duke Math. J. 3(3):460--472, 1937.

[52]

P. Mukkamala and M. Szegedy. Geometric representation of cubic graphs with four directions. Computational Geometry Theory & Applications 42(9):842--851, 2009.

Digital Library

[53]

J. Pach and D. Pálvölgyi. Bounded degree graphs can have arbitrarily large slope numbers. Electronic Journal of Combinatorics 13(1), 2006, http://www.combinatorics.org/Volume_13/PDF/v13i1n1.pdf.

[54]

M. S. Rahman, T. Nishizeki, and M. Naznin. Orthogonal drawings of plane graphs without bends. J. Graph Algorithms & Applications 7(4):335--362, 2003, http://jgaa.info/accepted/2003/Rahman+2003.7.4.pdf.

[55]

E. Raisz. The rectangular statistical cartogram. Geographical Review 24(2):292--296, 1934.

[56]

I. Rinsma. Rectangular and orthogonal floorplans with required rooms areas and tree adjacency. Environment and Planning B: Planning and Design 15:111--118, 1988.

[57]

I. Rivin. A characterization of ideal polyhedra in hyperbolic 3-space. Annals of Mathematics 143(1):51--70, 1996.

[58]

W. Schnyder. Embedding planar graphs on the grid. Proc. 1st ACM-SIAM Symp. Discrete Algorithms, pp. 138--148, 1990.

Digital Library

[59]

E. Steinitz. Polyeder und Raumeinteilungen. Encyclopadie der mathematischen Wissenschaften, Band 3 (Geometries), pp. 1--139, 1922.

[60]

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3):421--444, 1987.

Digital Library

[61]

W. P. Thurston. Conway's tiling groups. Amer. Mathematical Monthly 97(8):757--773, 1990.

Digital Library

[62]

D. Waltz. Understanding line drawings of scenes with shadows. The Psychology of Computer Vision, pp. 19--91. McGraw-Hill, 1975.

[63]

D. R. Wood. Lower bounds for the number of bends in three-dimensional orthogonal graph drawings. J. Graph Algorithms & Applications 7(1):33--77, 2003, http://jgaa.info/accepted/2003/Wood2003.7.1.pdf.

[64]

D. R. Wood. Optimal three-dimensional orthogonal graph drawing in the general position model. Theoretical Computer Science 299(1-3):151--178, 2003. http://www.ms.unimelb.edu.au/~woodd/papers/Wood-TCS03.pdf.

Digital Library

[65]

G. K. H. Yeap and M. Sarrafzadeh. Sliceable floorplanning by graph dualization. SIAM Journal of Discrete Mathematics 8(2):258--280, 1995.

Digital Library

[66]

G. M. Ziegler. Lectures on Polytopes. Graduate Texts in Mathematics. Springer-Verlag, Berlin, Heidelberg, and New York, 152 edition, 1995.

Cited By

Karmakar NBiswas ANandy SBhattacharya B(2023)On the Construction of Planar Embedding for a Class of Orthogonal PolyhedraCombinatorial Image Analysis10.1007/978-3-031-23612-9_6(84-104)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-23612-9_6
Pietroni NCampen MSheffer ACherchi GBommes DGao XScateni RLedoux FRemacle JLivesu M(2022)Hex-Mesh Generation and Processing: A SurveyACM Transactions on Graphics10.1145/355492042:2(1-44)Online publication date: 18-Oct-2022
https://dl.acm.org/doi/10.1145/3554920
Pietroni NCampen MSheffer ACherchi GBommes DGao XScateni RLedoux FRemacle JLivesu MJung S(2022)A Course on Hex-Mesh Generation and ProcessingSIGGRAPH Asia 2022 Courses10.1145/3550495.3558207(1-78)Online publication date: 6-Dec-2022
https://dl.acm.org/doi/10.1145/3550495.3558207
Show More Cited By

Index Terms

Steinitz theorems for orthogonal polyhedra
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph enumeration
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Extending Steinitz’s Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra

In 1922, 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 ...
On the Construction of Planar Embedding for a Class of Orthogonal Polyhedra
Combinatorial Image Analysis
Abstract
2D-representations of 3D digital objects find versatile applications to computer vision, robotics, medical imaging, and in discrete geometry. This work presents an algorithm for constructing a planar embedding with only straight-line edges for a ...
Steinberg-like theorems for backbone colouring
Abstract
A function f : V ( G ) → { 1 , … , k } is a (proper) k-colouring of G if ∣ f ( u ) − f ( v ) ∣ ≥ 1, for every edge u v ∈ E ( G ). The chromatic number χ ( G ) is the smallest integer k for which there exists a proper k-...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

June 2010

452 pages

ISBN:9781450300162

DOI:10.1145/1810959

Program Chairs:
David Kirkpatrick
University of British Columbia, Canada
,
Joseph Mitchell
SUNY Stony Brook, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '10

Sponsor:

SoCG '10: Symposium on Computational Geometry

June 13 - 16, 2010

Utah, Snowbird, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
320
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Karmakar NBiswas ANandy SBhattacharya B(2023)On the Construction of Planar Embedding for a Class of Orthogonal PolyhedraCombinatorial Image Analysis10.1007/978-3-031-23612-9_6(84-104)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-23612-9_6
Pietroni NCampen MSheffer ACherchi GBommes DGao XScateni RLedoux FRemacle JLivesu M(2022)Hex-Mesh Generation and Processing: A SurveyACM Transactions on Graphics10.1145/355492042:2(1-44)Online publication date: 18-Oct-2022
https://dl.acm.org/doi/10.1145/3554920
Pietroni NCampen MSheffer ACherchi GBommes DGao XScateni RLedoux FRemacle JLivesu MJung S(2022)A Course on Hex-Mesh Generation and ProcessingSIGGRAPH Asia 2022 Courses10.1145/3550495.3558207(1-78)Online publication date: 6-Dec-2022
https://dl.acm.org/doi/10.1145/3550495.3558207
Dumery CProtais FMestrallet SBourcier CLedoux F(2022)Evocube: A Genetic Labelling Framework for Polycube‐MapsComputer Graphics Forum10.1111/cgf.1464941:6(467-479)Online publication date: 31-Aug-2022
https://doi.org/10.1111/cgf.14649
Mandad MChen RBommes DCampen M(2022)Intrinsic mixed-integer polycubes for hexahedral meshingComputer Aided Geometric Design10.1016/j.cagd.2022.10207894(102078)Online publication date: Mar-2022
https://doi.org/10.1016/j.cagd.2022.102078
Maffucci R(2022)On polyhedral graphs and their complementsAequationes mathematicae10.1007/s00010-022-00902-596:5(939-953)Online publication date: 18-Aug-2022
https://doi.org/10.1007/s00010-022-00902-5
Li LZhang PSmirnov DAbulnaga SSolomon J(2021)Interactive all-hex meshing via cuboid decompositionACM Transactions on Graphics10.1145/3478513.348056840:6(1-17)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480568
Guo HLiu XYan DLiu Y(2020)Cut-enhanced PolyCube-maps for feature-aware all-hex meshingACM Transactions on Graphics10.1145/3386569.339237839:4(106:1-106:14)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392378
Zhao HLi XWang WWang XWang SLei NGu X(2019)Polycube Shape SpaceComputer Graphics Forum10.1111/cgf.1383938:7(311-322)Online publication date: 14-Nov-2019
https://doi.org/10.1111/cgf.13839
Yang YFu XLiu L(2019)Computing Surface PolyCube‐Maps by Constrained VoxelizationComputer Graphics Forum10.1111/cgf.1383838:7(299-309)Online publication date: 14-Nov-2019
https://doi.org/10.1111/cgf.13838
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents