A crossing Lemma for multigraphs
  • Metaadatok
Tartalom: http://real.mtak.hu/82753/
Archívum: REAL
Gyűjtemény: Status = Published
Type = Book Section
Subject = Q Science / természettudomány: QA Mathematics / matematika: QA166-QA166.245 Graphs theory / gráfelmélet
Cím:
A crossing Lemma for multigraphs
Létrehozó:
Pach, János
Tóth, Géza
Közreműködő:
Tóth, Csaba D.
Speckmann, B.
Kiadó:
Schloss Dagstuhl Leibniz-Zentrum für Informatik
Dátum:
2018
Téma:
QA166-QA166.245 Graphs theory / gráfelmélet
Tartalmi leírás:
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).
Nyelv:
angol
Típus:
Book Section
NonPeerReviewed
info:eu-repo/semantics/bookPart
Formátum:
text
Azonosító:
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
Kapcsolat:
MTMT:3403153; doi:10.4230/LIPIcs.SoCG.2018.65