Crossings between non-homotopic edges. (English) Zbl 1490.05189
Summary: A multigraph drawn in the plane is called non-homotopic if no pair of its edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the same way. Edges are allowed to intersect each other and themselves. It is easy to see that a non-homotopic multigraph on \(n > 1\) vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with \(n\) vertices and \(m > 4n\) edges is larger than \(c \frac{m^2}{n}\) for some constant \(c > 0\), and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as \(n\) is fixed and \(m\) tends to infinity.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 52C10 | Erdős problems and related topics of discrete geometry |
References:
| [1] | Ackerman, E., On topological graphs with at most four crossings per edge, Comput. Geom., 85, Article 101574 pp. (2019), 31 pp. · Zbl 1439.05163 |
| [2] | Ajtai, M.; Chvátal, V.; Newborn, M. N.; Szemerédi, E., Crossing-free subgraphs, (Theory and Practice of Combinatorics. Theory and Practice of Combinatorics, North-Holland Mathematics Studies, vol. 60 (1982), North-Holland: North-Holland Amsterdam), 9-12 · Zbl 0502.05021 |
| [3] | Aougab, T.; Souto, J., Counting curve types, Am. J. Math., 140, 1423-1441 (2018) · Zbl 1410.57015 |
| [4] | Dey, T. L., Improved bounds for planar k-sets and related problems, Discrete Comput. Geom., 19, 3, 373-382 (1998) · Zbl 0899.68107 |
| [5] | Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · JFM 61.0651.04 |
| [6] | Garey, M. R.; Johnson, D. S., Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods, 4, 3, 312-316 (1983) · Zbl 0536.05016 |
| [7] | Juvan, M.; Malnič, A.; Mohar, B., Systems of curves on surfaces, J. Comb. Theory, Ser. B, 68, 7-22 (1996) · Zbl 0859.57014 |
| [8] | Kaufmann, M.; Pach, J.; Tóth, G.; Ueckerdt, T., The number of crossings in multigraphs with no empty lens, (Graph Drawing and Network Visualization. Graph Drawing and Network Visualization, Lecture Notes in Comput. Sci., vol. 11282 (2018), Springer: Springer Cham), 242-254 · Zbl 1519.68194 |
| [9] | Leighton, T., Complexity Issues in VLSI, Foundations of Computing Series (1983), MIT Press: MIT Press Cambridge |
| [10] | Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 89 (1977), Springer-Verlag: Springer-Verlag Berlin-New York · Zbl 0368.20023 |
| [11] | Mirzakhani, M., Counting mapping class group orbits on hyperbolic surfaces (2016) |
| [12] | 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) · Zbl 1104.05022 |
| [13] | Pach, J.; Sharir, M., On the number of incidences between points and curves, Comb. Probab. Comput., 7, 1, 121-127 (1998) · Zbl 0901.52016 |
| [14] | Pach, J.; Tardos, G.; Tóth, G., Crossings between non-homotopic edges, (Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020) (2020)), 359-371 · Zbl 07436630 |
| [15] | Pach, J.; Tóth, G., Thirteen problems on crossing numbers, Geombinatorics, 9, 4, 199-207 (2000) · Zbl 0957.05026 |
| [16] | Pach, J.; Tóth, G., A crossing lemma for multigraphs, (Proc. 34th Annual Symposium on Computational Geometry (SoCG 2018), Vol. 65 (2018)), 1-13 · Zbl 1489.05033 |
| [17] | Pach, J.; Tóth, G., Graphs drawn with few crossings per edge, Combinatorica, 17, 427-439 (1997) · Zbl 0902.05017 |
| [18] | Schaefer, M., The graph crossing number and its variants: a survey, Electron. J. Comb., Dynamic Survey, DS21 (2013) · Zbl 1267.05180 |
| [19] | Schaefer, M., Crossing Numbers of Graphs (2018), CRC Press: CRC Press Boca Raton · Zbl 1388.05005 |
| [20] | Sharir, M.; Zahl, J., Cutting algebraic curves into pseudo-segments and applications, J. Comb. Theory, Ser. A, 150, 1-35 (2017) · Zbl 1362.05037 |
| [21] | Solymosi, J.; Tóth, C. D., Distinct distances in homogeneous sets in Euclidean space, Discrete Comput. Geom., 35, 4, 537-549 (2006) · Zbl 1102.52008 |
| [22] | Székely, L. A., Crossing numbers and hard Erdős problems in discrete geometry, Comb. Probab. Comput., 6, 3, 353-358 (1997) · Zbl 0882.52007 |
| [23] | Székely, L. A., A successful concept for measuring non-planarity of graphs: the crossing number, 6th International Conference on Graph Theory. 6th International Conference on Graph Theory, Discrete Math., 276, 1-3, 331-352 (2004) · Zbl 1035.05034 |
| [24] | Turán, P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48, 436-452 (1941), (in Hungarian) · Zbl 0026.26903 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
