A Crossing Lemma for the pair-crossing number

被引：1

作者：

Ackerman, Eyal ^{[1
]}

Schaefer, Marcus ^{[2
]}

机构：

[1] Dept. Math., Physics, and Comp. Sci, University of Haifa at Oranim, Tivon

[2] School of Computing, DePaul University, Chicago, 60604, IL

来源：

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 2014年 / 8871卷

关键词：

Crossing number - Graph G;

D O I：

10.1007/978-3-662-45803-7_19

中图分类号：

学科分类号：

摘要：

The pair-crossing number of a graph G, pcr(G), is the minimum possible number of pairs of edges that cross each other (possibly several times) in a drawing of G. It is known that there is a constant c ≥ 1/64 such that for every (not too sparse) graph G with n vertices and m edges pcr(G) ≥ c m3/n2. This bound is tight, up to the constant c. Here we show that c ≥ 1/34.2 if G is drawn without adjacent crossings. © Springer-Verlag Berlin Heidelberg 2014.

引用

页码：222 / 233

页数：11

共 15 条

[1]

Ackerman E., On Topological Graphs with at Most Four Crossings per Edge

[2]

Ackerman E., Tardos G., On the maximum number of edges in quasi-planar graphs, J. Combinatorial Theory, 114, 3, pp. 563-571, (2007)

[3]

Aigner M., Ziegler G., Proofs from the Book, (2004)

[4]

Ajtai M., Chvatal V., Newborn M., Szemeredi E., Crossing-free subgraphs, Theory and Practice of Combinatorics, 60, pp. 9-12, (1982)

[5]

Cranston D.W., West D.B., A Guide to Discharging (Manuscript)

[6]

Leighton F.T., Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks, Cambridge, (1983)

[7]

Matoussek J., Near-Optimal Separators in String Graphs, (2013)

[8]

Montaron B., An improvement of the crossing number bound, J. Graph Theory, 50, 1, pp. 43-54, (2005)

[9]

Pach J., Radoicic R., Tardos G., Toth G., Improving the crossing lemma by finding more crossings in sparse graphs. Disc, Compu. Geometry, 36, 4, pp. 527-552, (2006)

[10]

Pach J., Tóth, G.: Graphs drawn with few crossings per edge, Combinatorica, 17, 3, pp. 427-439, (1997)

← 1 2 →