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

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)

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

• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1452728 (Why is no real title available?)
• 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
• 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
• The number of crossings in multigraphs with no empty lens
• A bipartite strengthening of the crossing Lemma
• On the maximum number of crossings in star-simple drawings of \(K_n\) with no empty lens
• A Bipartite Strengthening of the Crossing Lemma
• Crossings between non-homotopic edges
• scientific article; zbMATH DE number 3914340 (Why is no real title available?)
• 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)