Skip to main content
SpringerLink
Log in

The Book Thickness of 1-Planar Graphs is Constant

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In a book embedding, the vertices of a graph are placed on the “spine” of a book and the edges are assigned to “pages”, so that edges on the same page do not cross. In this paper, we prove that every 1-planar graph (that is, a graph that can be drawn on the plane such that no edge is crossed more than once) admits an embedding in a book with constant number of pages. To the best of our knowledge, the best non-trivial previous upper-bound is \(O(\sqrt{n})\), where n is the number of vertices of the graph.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. We will shortly adjust this choice for two special cases. However, since we do not seek to enter into further details at this point, we assume for now that the choice is, in general, arbitrary.

  2. The term yields from the observation that along the boundary of the block-tree a 2-hop can “bypass” only one vertex because of maximal 1-planarity.

References

  1. Alam, J., Brandenbur, F.J., Kobourov, S.G.: Straight-line grid drawings of 3-connected 1-planar graphs. In: Graph Drawing, vol. 8242 of LNCS, pp. 83–94. Springer, Berlin (2013)

  2. Bekos, M.A,, Gronemann, M., Raftopoulou, C.N.: Two-page book embeddings of 4-planar graphs. In: STACS, vol. 25 of LIPIcs, pp. 137–148. Schloss Dagstuhl, Wadern (2014)

  3. Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Combin. Theory Ser. B 27(3), 320–331 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bilski, T.: Embedding graphs in books: a survey. IEEE Proc. Comput. Digit. Techn. 139(2), 134–138 (1992)

    Article  MathSciNet  Google Scholar 

  5. Bodendiek, R., Schumacher, H., Wagner, K.: Über 1-optimale graphen. Math. Nachr. 117(1), 323–339 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  6. Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. CoRR, abs/1203.5944 (2012)

  7. Cornuéjols, G., Naddef, D., Pulleyblank, W.R.: Halin graphs and the travelling salesman problem. Math. Program. 26(3), 287–294 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  8. Dujmovic, V., Wood, D.R.: Graph treewidth and geometric thickness parameters. Discrete Comput. Geom. 37(4), 641–670 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  10. Heath, L.: Embedding planar graphs in seven pages. In: FOCS, pp. 74–83. IEEE, New York (1984)

  11. Heath, L.S.: Algorithms for embedding graphs in books. Ph.D. thesis, University of North Carolina (1985)

  12. Fabrici, I., Madaras, T.: The structure of 1-planar graphs. Disc. Math. 307(7–8), 854–865 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  13. Kainen, P.C., Overbay, S.: Extension of a theorem of whitney. AML 20(7), 835–837 (2007)

    MathSciNet  MATH  Google Scholar 

  14. Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory 72(1), 30–71 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Malitz, S.M.: Genus \(g\) graphs have pagenumber \(o(\sqrt{q})\). J. Algorithms 17(1), 85–109 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  16. Malitz, S.M.: Graphs with \(e\) edges have pagenumber \(o(\sqrt{E})\). J. Algorithms 17(1), 71–84 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  17. Nesetril, J., Ossona de Mendez, P.: Sparsity: graphs, structures, and algorithms. In: Algorithms and Combinatorics, vol. 28. Springer, New York (2012)

  18. Nishizeki, T., Chiba, N.: Planar graphs: theory and algorithms, Chap. 10. In: Hamiltonian Cycles, pp. 171–184. Dover, New York (2008)

  19. Ollmann, T.L.: On the book thicknesses of various graphs. In: Proceedings of 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. 8 of Congressus Numerantium, p. 459 (1973)

  20. Overbay, S.: Graphs with small book thickness. Mo. J. Math. Sci. 19(2), 121–130 (2007)

    MATH  Google Scholar 

  21. Pach, J., Tóth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427–439 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  22. Whitney, H.: A theorem on graphs. Ann. Math. 32, 378–390 (1931)

    Article  MathSciNet  MATH  Google Scholar 

  23. Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36–67 (1989)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We thank S. Kobourov and J. Toenniskoetter for useful discussions. We also thank David R. Wood for pointing out an error in the first version of this paper.

Author information

Authors and Affiliations

  1. Wilhelm-Schickhard-Institut für Informatik, Universität Tübingen, Tübingen, Germany

    Michael A. Bekos, Till Bruckdorfer & Michael Kaufmann

  2. School of Applied Mathematical and Physical Sciences, NTUA, Athens, Greece

    Chrysanthi N. Raftopoulou

Authors
  1. Michael A. Bekos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Till Bruckdorfer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael Kaufmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Chrysanthi N. Raftopoulou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael A. Bekos.

Additional information

This article is based on the preliminary version: [Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann and Chrysanthi N. Raftopoulou: 1-Planar Graphs have Constant Book Thickness. In N. Bansal and I. Finocchi editors, Proc. of 23rd European Symposium on Algorithms (ESA 2015), LNCS 9294, pp. 130–141, 2015].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bekos, M.A., Bruckdorfer, T., Kaufmann, M. et al. The Book Thickness of 1-Planar Graphs is Constant. Algorithmica 79, 444–465 (2017). https://doi.org/10.1007/s00453-016-0203-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0203-2

Keywords

Search

Navigation