REAL

A crossing Lemma for multigraphs

Pach, János and Tóth, Géza (2018) A crossing Lemma for multigraphs. In: 34th International Symposium on Computational Geometry, SoCG 2018. Leibniz International Proceedings in Informatics, LIPIcs (99). Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, pp. 651-6513. ISBN 9783959770668

[img]
Preview
Text
1801.00721v1.pdf

Download (215kB) | Preview

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 ce3/n2, for a suitable constant c > 0. Ina seminal paper, Székely generalized this result to multigraphs, establishing the lower bound ce3/mn2, 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'e3/n2 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. © János Pach and Géza Tóth; licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).

Item Type: Book Section
Uncontrolled Keywords: Computational geometry; Separator theorems; Multigraphs; Maximum multiplicity; LOWER BOUNDS; Independent edges; Directed graphs; Computation theory; SEPARATOR THEOREM; multigraph; Crossing number; Crossing lemma
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 16 Aug 2018 13:30
Last Modified: 16 Aug 2018 13:30
URI: http://real.mtak.hu/id/eprint/82753

Actions (login required)

Edit Item Edit Item