Document Open Access Logo

Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

Authors Michael A. Bekos , Giordano Da Lozzo , Svenja M. Griesbach, Martin Gronemann , Fabrizio Montecchiani , Chrysanthi Raftopoulou

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.16.pdf
  • Filesize: 0.99 MB
  • 17 pages

Document Identifiers

Author Details

Michael A. Bekos
  • Department of Computer Science, University of Tübingen, Germany
Giordano Da Lozzo
  • Department of Engineering, Roma Tre University, Rome, Italy
Svenja M. Griesbach
  • Department of Mathematics and Computer Science, University of Cologne, Germany
Martin Gronemann
  • Department of Mathematics and Computer Science, University of Cologne, Germany
Fabrizio Montecchiani
  • Department of Engineering, University of Perugia, Italy
Chrysanthi Raftopoulou
  • School of Applied Mathematical & Physical Sciences, NTUA, Athens, Greece

Funding

  • Bekos, Michael A.: Partially supported by DFG grant KA812/18-1.
  • Da Lozzo, Giordano: Partially supported by MSCA-RISE project "CONNECT", N^∘ 734922, and by MIUR, grant 20174LF3T8 "AHeAD: efficient Algorithms for HArnessing networked Data".
  • Montecchiani, Fabrizio: Partially supported by MIUR, grant 20174LF3T8 "AHeAD: efficient Algorithms for HArnessing networked Data", and by Dipartimento di Ingegneria, Università degli studi di Perugia, grant RICBA19FM: "Modelli, algoritmi e sistemi per la visualizzazione di grafi e reti".

Acknowledgements

This work began at the Dagstuhl Seminar 19092 "Beyond-Planar Graphs: Combinatorics, Models and Algorithms" (February 24 - March 1, 2019).

Cite AsGet BibTex

Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou. Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.16

Abstract

An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar and all optimal 2-planar graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph algorithms
Keywords
  • Book embeddings
  • Book thickness
  • Nonplanar graphs
  • Planar skeleton

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, and Quanquan C. Liu. Upward partitioned book embeddings. In Graph Drawing, volume 10692 of LNCS, pages 210-223. Springer, 2017. Google Scholar
  2. Md. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov. Straight-line grid drawings of 3-connected 1-planar graphs. In Stephen K. Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of LNCS, pages 83-94. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-03841-4_8.
  3. Md. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov. On the book thickness of 1-planar graphs. CoRR, abs/1510.05891, 2015. URL: http://arxiv.org/abs/1510.05891.
  4. Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann, and Chrysanthi N. Raftopoulou. The book thickness of 1-planar graphs is constant. Algorithmica, 79(2):444-465, 2017. URL: https://doi.org/10.1007/s00453-016-0203-2.
  5. Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou. Book embeddings of nonplanar graphs with small faces in few pages. CoRR, abs/2003.07655, 2020. URL: http://arxiv.org/abs/2003.07655.
  6. Michael A. Bekos, Martin Gronemann, and Chrysanthi N. Raftopoulou. Two-page book embeddings of 4-planar graphs. Algorithmica, 75(1):158-185, 2016. URL: https://doi.org/10.1007/s00453-015-0016-8.
  7. Michael A. Bekos, Michael Kaufmann, and Chrysanthi N. Raftopoulou. On optimal 2- and 3-planar graphs. In Boris Aronov and Matthew J. Katz, editors, SoCG, volume 77 of LIPIcs, pages 16:1-16:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.16.
  8. Frank Bernhart and Paul C. Kainen. The book thickness of a graph. J. Comb. Theory, Ser. B, 27(3):320-331, 1979. URL: https://doi.org/10.1016/0095-8956(79)90021-2.
  9. Therese C. Biedl, Thomas C. Shermer, Sue Whitesides, and Stephen K. Wismath. Bounds for orthogonal 3D graph drawing. J. Graph Algorithms Appl., 3(4):63-79, 1999. URL: https://doi.org/10.7155/jgaa.00018.
  10. Carla Binucci, Giordano Da Lozzo, Emilio Di Giacomo, Walter Didimo, Tamara Mchedlidze, and Maurizio Patrignani. Upward book embeddings of st-graphs. In SoCG, volume 129 of LIPIcs, pages 13:1-13:22. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.13.
  11. Robin L. Blankenship. Book Embeddings of Graphs. PhD thesis, Louisiana State University, 2003. Google Scholar
  12. Franz J. Brandenburg. Characterizing and recognizing 4-map graphs. Algorithmica, 81(5):1818-1843, 2019. URL: https://doi.org/10.1007/s00453-018-0510-x.
  13. Jonathan F. Buss and Peter W. Shor. On the pagenumber of planar graphs. In Richard A. DeMillo, editor, ACM Symposium on Theory of Computing, pages 98-100. ACM, 1984. URL: https://doi.org/10.1145/800057.808670.
  14. Fan R. K. Chung, Frank T. Leighton, and Arnold L. Rosenberg. Embedding graphs in books: A layout problem with applications to VLSI design. SIAM Journal on Algebraic and Discrete Methods, 8(1):33-58, 1987. Google Scholar
  15. Gérard Cornuéjols, Denis Naddef, and William R. Pulleyblank. Halin graphs and the travelling salesman problem. Math. Program., 26(3):287-294, 1983. URL: https://doi.org/10.1007/BF02591867.
  16. Giordano Da Lozzo, Vít Jelínek, Jan Kratochvíl, and Ignaz Rutter. Planar embeddings with small and uniform faces. In Hee-Kap Ahn and Chan-Su Shin, editors, ISAAC, volume 8889 of LNCS, pages 633-645. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-13075-0_50.
  17. Hubert de Fraysseix, Patrice Ossona de Mendez, and János Pach. A left-first search algorithm for planar graphs. Discrete & Computational Geometry, 13:459-468, 1995. URL: https://doi.org/10.1007/BF02574056.
  18. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. Google Scholar
  19. Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity. ACM Comput. Surv., 52(1):4:1-4:37, 2019. URL: https://doi.org/10.1145/3301281.
  20. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  21. Vida Dujmović and Fabrizio Frati. Stack and queue layouts via layered separators. J. Graph Algorithms Appl., 22(1):89-99, 2018. URL: https://doi.org/10.7155/jgaa.00454.
  22. Vida Dujmovic, Pat Morin, and David R. Wood. Layered separators in minor-closed graph classes with applications. J. Comb. Theory, Ser. B, 127:111-147, 2017. URL: https://doi.org/10.1016/j.jctb.2017.05.006.
  23. Vida Dujmović and David R. Wood. Graph treewidth and geometric thickness parameters. Discrete & Computational Geometry, 37(4):641-670, 2007. URL: https://doi.org/10.1007/s00454-007-1318-7.
  24. Günter Ewald. Hamiltonian circuits in simplicial complexes. Geometriae Dedicata, 2(1):115-125, 1973. URL: https://doi.org/10.1007/BF00149287.
  25. Joseph L. Ganley and Lenwood S. Heath. The pagenumber of k-trees is O(k). Discrete Applied Mathematics, 109(3):215-221, 2001. URL: https://doi.org/10.1016/S0166-218X(00)00178-5.
  26. Xiaxia Guan and Weihua Yang. Embedding 5-planar graphs in three pages. CoRR, 1801.07097, 2018. URL: http://arxiv.org/abs/1801.07097.
  27. Lenwood S. Heath. Embedding planar graphs in seven pages. In FOCS, pages 74-83. IEEE Computer Society, 1984. URL: https://doi.org/10.1109/SFCS.1984.715903.
  28. Michael Hoffmann and Boris Klemz. Triconnected planar graphs of maximum degree five are subhamiltonian. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, ESA, volume 144 of LIPIcs, pages 58:1-58:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.58.
  29. Sorin Istrail. An algorithm for embedding planar graphs in six pages. Iasi University Annals, Mathematics-Computer Science, 34(4):329-341, 1988. Google Scholar
  30. Guy Jacobson. Space-efficient static trees and graphs. In Symposium on Foundations of Computer Science, pages 549-554. IEEE Computer Society, 1989. URL: https://doi.org/10.1109/SFCS.1989.63533.
  31. Paul C. Kainen and Shannon Overbay. Extension of a theorem of whitney. Appl. Math. Lett., 20(7):835-837, 2007. URL: https://doi.org/10.1016/j.aml.2006.08.019.
  32. Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani. An annotated bibliography on 1-planarity. Computer Science Review, 25:49-67, 2017. URL: https://doi.org/10.1016/j.cosrev.2017.06.002.
  33. Seth M. Malitz. Genus g graphs have pagenumber O(√q). J. Algorithms, 17(1):85-109, 1994. URL: https://doi.org/10.1006/jagm.1994.1028.
  34. Seth M. Malitz. Graphs with E edges have pagenumber O(√E). J. Algorithms, 17(1):71-84, 1994. URL: https://doi.org/10.1006/jagm.1994.1027.
  35. J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses and static trees. SIAM J. Comput., 31(3):762-776, 2001. URL: https://doi.org/10.1137/S0097539799364092.
  36. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  37. Takao Nishizeki and Norishige Chiba. Planar Graphs: Theory and Algorithms, chapter 10. Hamiltonian Cycles, pages 171-184. Dover Books on Mathematics. Courier Dover Publications, 2008. Google Scholar
  38. Taylor Ollmann. On the book thicknesses of various graphs. In F. Hoffman, R.B. Levow, and R.S.D. Thomas, editors, Southeastern Conference on Combinatorics, Graph Theory and Computing, volume VIII of Congressus Numerantium, page 459, 1973. Google Scholar
  39. Vaughan R. Pratt. Computing permutations with double-ended queues, parallel stacks and parallel queues. In Alfred V. Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Harrison, Richard M. Karp, and H. Raymond Strong, editors, ACM Symposium on Theory of Computing, pages 268-277. ACM, 1973. URL: https://doi.org/10.1145/800125.804058.
  40. S. Rengarajan and C. E. Veni Madhavan. Stack and queue number of 2-trees. In Ding-Zhu Du and Ming Li, editors, COCOON, volume 959 of LNCS, pages 203-212. Springer, 1995. URL: https://doi.org/10.1007/BFb0030834.
  41. Gerhard Ringel. Ein Sechsfarbenproblem auf der kugel. Abhandlungen aus dem Mathematischen Seminar der Universitaet Hamburg, 29(1-2):107-117, 1965. Google Scholar
  42. Arnold L. Rosenberg. The diogenes approach to testable fault-tolerant arrays of processors. IEEE Trans. Computers, 32(10):902-910, 1983. URL: https://doi.org/10.1109/TC.1983.1676134.
  43. Robert E. Tarjan. Sorting using networks of queues and stacks. J. ACM, 19(2):341-346, 1972. URL: https://doi.org/10.1145/321694.321704.
  44. Avi Wigderson. The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical Report TR-298, EECS Department, Princeton University, 1982. URL: http://arxiv.org/abs/https://www.math.ias.edu/avi/node/820.
  45. David R. Wood. Degree constrained book embeddings. J. Algorithms, 45(2):144-154, 2002. URL: https://doi.org/10.1016/S0196-6774(02)00249-3.
  46. Mihalis Yannakakis. Four pages are necessary and sufficient for planar graphs (extended abstract). In Juris Hartmanis, editor, ACM Symposium on Theory of Computing, pages 104-108. ACM, 1986. URL: https://doi.org/10.1145/12130.12141.
  47. Mihalis Yannakakis. Embedding planar graphs in four pages. J. Comput. Syst. Sci., 38(1):36-67, 1989. URL: https://doi.org/10.1016/0022-0000(89)90032-9.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact