Document Open Access Logo

Beyond-Planarity: Turán-Type Results for Non-Planar Bipartite Graphs

Authors Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, Maximilian Pfister, Torsten Ueckerdt

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.28.pdf
  • Filesize: 0.69 MB
  • 13 pages

Document Identifiers

Author Details

Patrizio Angelini
  • Wilhelm-Schickhard-Institut für Informatik, Universität Tübingen, Germany
Michael A. Bekos
  • Wilhelm-Schickhard-Institut für Informatik, Universität Tübingen, Germany
Michael Kaufmann
  • Wilhelm-Schickhard-Institut für Informatik, Universität Tübingen, Germany
Maximilian Pfister
  • Wilhelm-Schickhard-Institut für Informatik, Universität Tübingen, Germany
Torsten Ueckerdt
  • Fakultät für Informatik, KIT, Karlsruhe, Germany

Funding

This project was supported by DFG grant KA812/18-1.

Cite As Get BibTex

Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, Maximilian Pfister, and Torsten Ueckerdt. Beyond-Planarity: Turán-Type Results for Non-Planar Bipartite Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.28

Abstract

Beyond-planarity focuses on the study of geometric and topological graphs that are in some sense nearly planar. Here, planarity is relaxed by allowing edge crossings, but only with respect to some local forbidden crossing configurations. Early research dates back to the 1960s (e.g., Avital and Hanani 1966) for extremal problems on geometric graphs, but is also related to graph drawing problems where visual clutter due to edge crossings should be minimized (e.g., Huang et al. 2018).
Most of the literature focuses on Turán-type problems, which ask for the maximum number of edges a beyond-planar graph can have. Here, we study this problem for bipartite topological graphs, considering several types of beyond-planar graphs, i.e. 1-planar, 2-planar, fan-planar, and RAC graphs. We prove bounds on the number of edges that are tight up to additive constants; some of them are surprising and not along the lines of the known results for non-bipartite graphs. Our findings lead to an improvement of the leading constant of the well-known Crossing Lemma for bipartite graphs, as well as to a number of interesting questions on topological graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph theory
Keywords
  • Bipartite topological graphs
  • beyond planarity
  • density
  • Crossing Lemma

Metrics

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

Related Versions

References

  1. Eyal Ackerman. On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing Edges. Discrete Comput. Geom., 41(3):365-375, 2009. URL: http://dx.doi.org/10.1007/s00454-009-9143-9.
  2. Eyal Ackerman. On topological graphs with at most four crossings per edge. CoRR, abs/1509.01932, 2015. URL: http://arxiv.org/abs/1509.01932.
  3. Pankaj K. Agarwal, Boris Aronov, János Pach, Richard Pollack, and Micha Sharir. Quasi-Planar Graphs Have a Linear Number of Edges. Combinatorica, 17(1):1-9, 1997. URL: http://dx.doi.org/10.1007/BF01196127.
  4. Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK (3rd. ed.). Springer, 2004. Google Scholar
  5. M. Ajtai, V. Chvátal, M. Newborn, and E. Szemerédi. Crossing-free sub-graphs. Annals of Discrete Mathematics, 12:9-12, 1982. Google Scholar
  6. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov. Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs. In Graph Drawing, volume 8242 of LNCS, pages 83-94. Springer, 2013. Google Scholar
  7. Noga Alon and Paul Erdős. Disjoint Edges in Geometric Graphs. Discrete Comput. Geom., 4:287-290, 1989. URL: http://dx.doi.org/10.1007/BF02187731.
  8. Patrizio Angelini, Michael A. Bekos, Franz J. Brandenburg, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, and Ignaz Rutter. On the Relationship between k-Planar and k-Quasi Planar Graphs. In WG, volume 10520 of LNCS, pages 59-74. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-68705-6_5.
  9. Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, Maximilian Pfister, and Torsten Ueckerdt. Beyond-Planarity: Density Results for Bipartite Graphs. CoRR, abs/1712.09855, 2017. URL: http://arxiv.org/abs/1712.09855.
  10. Evmorfia N. Argyriou, Michael A. Bekos, and Antonios Symvonis. The Straight-Line RAC Drawing Problem is NP-Hard. J. Graph Algor. Appl., 16(2):569-597, 2012. URL: http://dx.doi.org/10.7155/jgaa.00274.
  11. Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber. Outer 1-Planar Graphs. Algorithmica, 74(4):1293-1320, 2016. Google Scholar
  12. S. Avital and H. Hanani. Graphs. Gilyonot Lematematika, 3:2-8, 1966. Google Scholar
  13. Michael A. Bekos, Michael Kaufmann, and Chrysanthi N. Raftopoulou. On the Density of Non-simple 3-Planar Graphs. In Graph Drawing, volume 9801 of LNCS, pages 344-356. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-50106-2_27.
  14. Carla Binucci, Emilio Di Giacomo, Walter Didimo, Fabrizio Montecchiani, Maurizio Patrignani, Antonios Symvonis, and Ioannis G. Tollis. Fan-planarity: Properties and complexity. Theor. Comp. Sci., 589:76-86, 2015. Google Scholar
  15. B. Bollobás. Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability. Cambridge University Press, 1986. Google Scholar
  16. Franz J. Brandenburg. Recognizing Optimal 1-Planar Graphs in Linear Time. Algorithmica, 80(1):1-28, 2018. URL: http://dx.doi.org/10.1007/s00453-016-0226-8.
  17. Franz J. Brandenburg, Walter Didimo, William Evans, Philipp Kindermann, Giuseppe Liotta, and Fabrizio Montecchiani. Recognizing and drawing IC-planar graphs. Theor. Comp. Sci., 636:1-16, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.04.026.
  18. Július Czap, Jakub Przybyło, and Erika Škrabul'áková. On an extremal problem in the class of bipartite 1-planar graphs. Discussiones Mathematicae Graph Theory, 36(1):141-151, 2016. Google Scholar
  19. Walter Didimo, Peter Eades, and Giuseppe Liotta. A characterization of complete bipartite RAC graphs. Inf. Process. Lett., 110(16):687-691, 2010. URL: http://dx.doi.org/10.1016/j.ipl.2010.05.023.
  20. Walter Didimo, Peter Eades, and Giuseppe Liotta. Drawing graphs with right angle crossings. Theor. Comp. Sci., 412(39):5156-5166, 2011. Google Scholar
  21. Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A Survey on Graph Drawing Beyond Planarity. CoRR, abs/1804.07257, 2018. URL: http://arxiv.org/abs/1804.07257.
  22. Peter Eades and Giuseppe Liotta. Right angle crossing graphs and 1-planarity. Discrete Appl. Math., 161(7-8):961-969, 2013. URL: http://dx.doi.org/10.1016/j.dam.2012.11.019.
  23. Paul Erdős. On some extremal problems in graph theory. Israel J. Math., 3:113-116, 1965. Google Scholar
  24. Jacob Fox, János Pach, and Andrew Suk. The Number of Edges in k-Quasi-planar Graphs. SIAM J. Discrete Math., 27(1):550-561, 2013. URL: http://dx.doi.org/10.1137/110858586.
  25. Michael Hoffmann and Csaba D. Tóth. Two-Planar Graphs Are Quasiplanar. In MFCS, volume 83 of LIPIcs, pages 47:1-47:14. Schloss Dagstuhl, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.47.
  26. Seok-Hee Hong, Peter Eades, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer, and Yusuke Suzuki. A Linear-Time Algorithm for Testing Outer-1-Planarity. Algorithmica, 72(4):1033-1054, 2015. Google Scholar
  27. John E. Hopcroft and Robert Endre Tarjan. Efficient Planarity Testing. J. ACM, 21(4):549-568, 1974. URL: http://dx.doi.org/10.1145/321850.321852.
  28. Weidong Huang, Seok-Hee Hong, and Peter Eades. Effects of Crossing Angles. In PacificVis 2008, pages 41-46. IEEE, 2008. Google Scholar
  29. D. V. Karpov. An Upper Bound on the Number of Edges in an Almost Planar Bipartite Graph. Journal of Mathematical Sciences, 196(6):737-746, 2014. Google Scholar
  30. Michael Kaufmann and Torsten Ueckerdt. The Density of Fan-Planar Graphs. CoRR, 1403.6184, 2014. URL: http://arxiv.org/abs/1403.6184.
  31. Frank Thomson Leighton. Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge, MA, USA, 1983. Google Scholar
  32. János Pach, Radoš Radoičić, Gábor Tardos, and Géza Tóth. Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs. Discrete Comput. Geom., 36(4):527-552, 2006. Google Scholar
  33. János Pach and Géza Tóth. Graphs Drawn with Few Crossings per Edge. Combinatorica, 17(3):427-439, 1997. URL: http://dx.doi.org/10.1007/BF01215922.
  34. Gerhard Ringel. Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamb., 29:107-117, 1965. Google Scholar
  35. Yusuke Suzuki. Re-embeddings of Maximum 1-Planar Graphs. SIAM J. Discrete Math., 24(4):1527-1540, 2010. URL: http://dx.doi.org/10.1137/090746835.
  36. Kazimierz Zarankiewicz. On a Problem of P. Turán Concerning Graphs. Fundamenta Mathematicae, 41:137-145, 1954. Google Scholar
  37. Xin Zhang. Drawing complete multipartite graphs on the plane with restrictions on crossings. Acta Mathematica Sinica, English Series, 30(12):2045-2053, 2014. Google Scholar
  38. Xin Zhang and Guizhen Liu. The structure of plane graphs with independent crossings and its applications to coloring problems. Central Eur. J. of Mathematics, 11(2):308-321, 2013. Google Scholar
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 About DROPS Imprint Privacy Contact