Document Open Access Logo

On Optimal 2- and 3-Planar Graphs

Authors Michael A. Bekos, Michael Kaufmann, Chrysanthi N. Raftopoulou

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.16.pdf
  • Filesize: 1 MB
  • 16 pages

Document Identifiers

Author Details

Michael A. Bekos
Michael Kaufmann
Chrysanthi N. Raftopoulou

Cite AsGet BibTex

Michael A. Bekos, Michael Kaufmann, and Chrysanthi N. Raftopoulou. On Optimal 2- and 3-Planar Graphs. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.16

Abstract

A graph is k-planar if it can be drawn in the plane such that no edge is crossed more than k times. While for k=1, optimal 1-planar graphs, i.e., those with n vertices and exactly 4n-8 edges, have been completely characterized, this has not been the case for k > 1. For k=2,3 and 4, upper bounds on the edge density have been developed for the case of simple graphs by Pach and Tóth, Pach et al. and Ackerman, which have been used to improve the well-known "Crossing Lemma". Recently, we proved that these bounds also apply to non-simple 2- and 3-planar graphs without homotopic parallel edges and self-loops. In this paper, we completely characterize optimal 2- and 3-planar graphs, i.e., those that achieve the aforementioned upper bounds. We prove that they have a remarkably simple regular structure, although they might be non-simple. The new characterization allows us to develop notable insights concerning new inclusion relationships with other graph classes.
Keywords
  • topological graphs
  • optimal k-planar graphs
  • characterization

Metrics

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

References

  1. E. Ackerman. On topological graphs with at most four crossings per edge. CoRR, 1509.01932, 2015. Google Scholar
  2. M. Ajtai, V. Chvátal, M. Newborn, and E. Szemerédi. Crossing-free subgraphs. In Theory and Practice of Combinatorics, pages 9-12. North-Holland Mathematics Studies, 1982. Google Scholar
  3. N. Alon and P. Erdős. Disjoint edges in geometric graphs. Discrete & Computational Geometry, 4:287-290, 1989. URL: http://dx.doi.org/10.1007/BF02187731.
  4. P. Angelini, M. A. Bekos, F.-J. Brandenburg, G. Da Lozzo, G. Di Battista, W. Didimo, G. Liotta, F. Montecchiani, and I. Rutter. On the relationship between k-planar and k-quasi planar graphs. CoRR, 1702.08716, 2017. Google Scholar
  5. M. A. Bekos, T. Bruckdorfer, M. Kaufmann, and C. N. Raftopoulou. 1-planar graphs have constant book thickness. In ESA, volume 9294 of LNCS, pages 130-141. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_12.
  6. M. A. Bekos, M. Kaufmann, and C. 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.
  7. C. Binucci, E. Di Giacomo, W. Didimo, F. Montecchiani, M. Patrignani, A. Symvonis, and I. G. Tollis. Fan-planarity: Properties and complexity. Theor. Comp. Sci., 589:76-86, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.04.020.
  8. R. Bodendiek, H. Schumacher, and K. Wagner. Über 1-optimale Graphen. Mathematische Nachrichten, 117(1):323-339, 1984. Google Scholar
  9. O. Borodin. A new proof of the 6 color theorem. J. of Graph Theory, 19(4):507-521, 1995. URL: http://dx.doi.org/10.1002/jgt.3190190406.
  10. F.-J. Brandenburg. 1-visibility representations of 1-planar graphs. J. Graph Algorithms Appl., 18(3):421-438, 2014. URL: http://dx.doi.org/10.7155/jgaa.00330.
  11. F.-J. Brandenburg. Recognizing optimal 1-planar graphs in linear time. CoRR, 1602.08022, 2016. Google Scholar
  12. O. Cheong, S. Har-Peled, H. Kim, and H.-S. Kim. On the number of edges of fan-crossing free graphs. Algorithmica, 73(4):673-695, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9935-z.
  13. A. M. Dean, W. S. Evans, E. Gethner, J. D. Laison, M. A. Safari, and W. T. Trotter. Bar k-visibility graphs. J. Graph Algorithms Appl., 11(1):45-59, 2007. Google Scholar
  14. E. Di Giacomo, W. Didimo, G. Liotta, H. Meijer, and S. K. Wismath. Planar and quasi-planar simultaneous geometric embedding. Comput. J., 58(11):3126-3140, 2015. URL: http://dx.doi.org/10.1093/comjnl/bxv048.
  15. W. Didimo, P. Eades, and G. Liotta. Drawing graphs with right angle crossings. Theor. Comp. Sci., 412(39):5156-5166, 2011. Google Scholar
  16. S. Hong, P. Eades, G. Liotta, and S.-H. Poon. Fáry’s theorem for 1-planar graphs. In COCOON, volume 7434 of LNCS, pages 335-346. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32241-9_29.
  17. M. Kaufmann and T. Ueckerdt. The density of fan-planar graphs. CoRR, 1403.6184, 2014. Google Scholar
  18. T. Leighton. Complexity Issues in VLSI. Foundations of Computing Series. MIT Press., 1983. Google Scholar
  19. L. Lovász, J. Pach, and M. Szegedy. On Conway’s thrackle conjecture. Discrete & Computational Geometry, 18(4):369-376, 1997. URL: http://dx.doi.org/10.1007/PL00009322.
  20. A. Bekos M. M. Kaufmann, and N. Raftopoulou C.Ȯn optimal 2- and 3-planar graphs. CoRR, 1703.06526, 2017. Google Scholar
  21. J. Pach, R. Radoičić, G. Tardos, and G. Tóth. Improving the crossing lemma by finding more crossings in sparse graphs. Discrete & Computational Geometry, 36(4):527-552, 2006. URL: http://dx.doi.org/10.1007/s00454-006-1264-9.
  22. J. Pach and G. Tóth. Graphs drawn with few crossings per edge. Combinatorica, 17(3):427-439, 1997. URL: http://dx.doi.org/10.1007/BF01215922.
  23. G. Ringel. Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (in German), 29:107-117, 1965. Google Scholar
  24. Y. 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.
  25. P. Turán. A note of welcome. J. of Graph Theory, 1(1):7-9, 1977. URL: http://dx.doi.org/10.1002/jgt.3190010105.
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