A crossing lemma for multigraphs

DOI10.1007/s00454-018-00052-zzbMath1446.05026OpenAlexW2962914899WikidataQ125018615 ScholiaQ125018615MaRDI QIDQ2189737

János Pach, Géza Tóth

Publication date: 16 June 2020

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8778/

zbMATH Keywords

crossing numbercrossing lemmabisection widthseparator theorem

Mathematics Subject Classification ID

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

Related Items

On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens ⋮ On the number of edges of separated multigraphs ⋮ The number of crossings in multigraphs with no empty lens ⋮ Quantitative Restrictions on Crossing Patterns ⋮ On the Maximum Number of Crossings in Star-Simple Drawings of $$K_n$$ with No Empty Lens

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extremal problems in discrete geometry
• Improved bounds for planar \(k\)-sets and related problems
• A successful concept for measuring non-planarity of graphs: The crossing number.
• New bounds on crossing numbers
• The number of crossings in multigraphs with no empty lens
• Applications of the crossing number
• The graph crossing number and its variants: a survey
• Crossing Number is NP-Complete
• Crossing-Free Subgraphs
• Planar Separators
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry