A crossing lemma for multigraphs

DOI10.4230/LIPICS.SOCG.2018.65zbMATH Open1489.05033arXiv1801.00721MaRDI QIDQ5116525FDOQ5116525

János Pach, Géza Tóth

Publication date: 18 August 2020

Abstract: Let $G$ be a drawing of a graph with $n$ vertices and $e>4n$ 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'atal, Newborn, Szemer'edi and Leighton, the number of crossings in $G$ is at least $c{e}^{3}over{n}^2$, for a suitable constant $c>0$. In a seminal paper, Sz'ekely generalized this result to multigraphs, establishing the lower bound $c{e}^{3}overm{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^{\prime }{e}^{3}over{n}^2$ for some $c^{\prime }>0$, provided that the "lens" enclosed by every pair of parallel edges in $G$ contains at least one vertex. This settles a conjecture of Kaufmann.

Full work available at URL: https://arxiv.org/abs/1801.00721

zbMATH Keywords

multigraphcrossing numbercrossing lemmaseparator theorem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Extremal problems in discrete geometry
• Improved bounds for planar \(k\)-sets and related problems
• The graph crossing number and its variants: a survey
• Crossing Number is NP-Complete
• Crossing-Free Subgraphs
• Complexity of Some Geometric and Topological Problems
• Planar Separators
• Applications of the crossing number
• A successful concept for measuring non-planarity of graphs: The crossing number.
• Title not available (Why is that?)

Cited In (6)

• The number of crossings in multigraphs with no empty lens
• Crossings between non-homotopic edges
• Making a graph crossing-critical by multiplying its edges
• A crossing lemma for multigraphs
• Crossings Between Non-homotopic Edges
• Improving the crossing lemma by finding more crossings in sparse graphs

This page was built for publication: A crossing lemma for multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116525)