We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Crossing Lemma for Multigraphs.
- Authors
Pach, János; Tóth, Géza
- Abstract
Let G be a drawing of a graph with n vertices and e > 4 n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and Leighton, the number of crossings in G is at least c e 3 n 2 , for a suitable constant c > 0 . In a seminal paper, Székely generalized this result to multigraphs, establishing the lower bound c e 3 m n 2 , where m denotes the maximum multiplicity of an edge in G. We get rid of the dependence on m by showing that, as in the original Crossing Lemma, the number of crossings is at least c ′ e 3 n 2 for some c ′ > 0 , provided that the "lens" enclosed by every pair of parallel edges in G contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.
- Subjects
MULTIGRAPH; MULTIPLICITY (Mathematics); LOGICAL prediction; EDGES (Geometry); GEOMETRIC vertices; CROSSES
- Publication
Discrete & Computational Geometry, 2020, Vol 63, Issue 4, p918
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-018-00052-z