Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. A Crossing Lemma for Multigraphs
 
research article

A Crossing Lemma for Multigraphs

Pach, Janos  
•
Toth, Geza
June 1, 2020
Discrete & Computational Geometry

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, Chvatal, Newborn, Szemeredi 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, Szekely generalized this result to multigraphs, establishing the lower bound c e(3)/mn(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.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s00454-018-00052-z
Web of Science ID

WOS:000540210100008

Author(s)
Pach, Janos  
Toth, Geza
Date Issued

2020-06-01

Publisher

SPRINGER

Published in
Discrete & Computational Geometry
Volume

63

Issue

4

Start page

918

End page

933

Subjects

Computer Science, Theory & Methods

•

Mathematics

•

Computer Science

•

crossing number

•

crossing lemma

•

separator theorem

•

bisection width

•

bounds

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
June 28, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/169669
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés