A crossing lemma for multigraphs

DOI10.4230/LIPICS.SOCG.2018.65MaRDI QIDQ5116525zbMATH OpenFDO

Authors János Pach, Géza Tóth

Publication date 18 August 2020

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

zbMATH Keywords

crossing lemmacrossing numbermultigraphseparator theorem

Mathematics Subject Classification ID

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

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.

Recommendations

• A crossing lemma for multigraphs
• Improving the crossing lemma by finding more crossings in sparse graphs
• The number of crossings in multigraphs with no empty lens
• The number of crossings in multigraphs with no empty lens
• On topological graphs with at most four crossings per edge

Cites work

• A successful concept for measuring non-planarity of graphs: The crossing number.
• Applications of the crossing number
• Complexity of some geometric and topological problems
• Crossing Number is NP-Complete
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Crossing-Free Subgraphs
• Extremal problems in discrete geometry
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1452728 (Why is no real title available?)
• Improved bounds for planar k-sets and related problems
• Planar Separators
• The graph crossing number and its variants: a survey

Cited in

(11)

• The number of crossings in multigraphs with no empty lens
• Making a graph crossing-critical by multiplying its edges
• A crossing lemma for multigraphs
• Crossings between non-homotopic edges
• scientific article; zbMATH DE number 3914340 (Why is no real title available?)
• Crossings Between Non-homotopic Edges
• On the maximum number of crossings in star-simple drawings of \(K_n\) with no empty lens
• The number of crossings in multigraphs with no empty lens
• Improving the crossing lemma by finding more crossings in sparse graphs
• A Bipartite Strengthening of the Crossing Lemma
• A bipartite strengthening of the crossing Lemma

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)