Abstract
Every finite graph admits a simple (topological) drawing, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, k-planar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a k-plane drawing). It is known that for \(k\le 3\), every k-planar graph admits a k-plane simple drawing. But for \(k\ge 4\), there exist k-planar graphs that do not admit a k-plane simple drawing. Answering a question by Schaefer, we show that there exists a function such that every k-planar graph admits an f(k)-plane simple drawing, for all
. Note that the function f depends on k only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every 4-planar graph admits an 8-plane simple drawing.
This work was initiated at the \(17^{th}\) Gremo Workshop on Open Problems (GWOP) 2019. The authors thank the organizers of the workshop for inviting us and providing a productive working atmosphere. M. H. and M. M. R. are supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681. Research by C. D. T. was supported in part by the NSF award DMS-1800734.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ackerman, E.: On topological graphs with at most four crossings per edge. Comput. Geom. 85, 101574 (2019). https://doi.org/10.1016/j.comgeo.2019.101574
Pach, J., Radoičić, R., Tardos, G., Tóth, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom. 36(4), 527–552 (2006). https://doi.org/10.1007/s00454-006-1264-9
Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 29, 107–117 (1965). https://doi.org/10.1007/BF02996313
Schaefer, M.: The graph crossing number and its variants: a survey. Electron. J. Comb. 20 (2013). https://doi.org/10.37236/2713. Version 4 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Hoffmann, M., Liu, CH., Reddy, M.M., Tóth, C.D. (2020). Simple Topological Drawings of k-Planar Graphs. In: Auber, D., Valtr, P. (eds) Graph Drawing and Network Visualization. GD 2020. Lecture Notes in Computer Science(), vol 12590. Springer, Cham. https://doi.org/10.1007/978-3-030-68766-3_31
Download citation
DOI: https://doi.org/10.1007/978-3-030-68766-3_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-68765-6
Online ISBN: 978-3-030-68766-3
eBook Packages: Computer ScienceComputer Science (R0)