License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.65
URN: urn:nbn:de:0030-drops-87781
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8778/
Go to the corresponding LIPIcs Volume Portal

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

A Crossing Lemma for Multigraphs

pdf-format:
LIPIcs-SoCG-2018-65.pdf (0.5 MB)

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átal, Newborn, Szemerédi 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ékely generalized this result to multigraphs, establishing the lower bound c{e^3 over 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 over 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.

BibTeX - Entry

@InProceedings{pach_et_al:LIPIcs:2018:8778,
  author =	{J{\'a}nos Pach and G{\'e}za T{\'o}th},
  title =	{{A Crossing Lemma for Multigraphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8778},
  URN =		{urn:nbn:de:0030-drops-87781},
  doi =		{10.4230/LIPIcs.SoCG.2018.65},
  annote =	{Keywords: crossing number, Crossing Lemma, multigraph, separator theorem}
}

Keywords: crossing number, Crossing Lemma, multigraph, separator theorem
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI