Information Technology Reference
In-Depth Information
drawing of
G
inherited from the drawing of
G
.Then
E
[pcr
+
(
G
)]
≤
E
[
x
]=
p
4
·
pcr
+
(
G
).
3
It follows from Theorem 6 that pcr
+
(
G
)
≥
pcr(
G
)
≥
4
m
−
18
n
(note that this it true for any
n
≥
0), and this holds also for the expected
values:
E
[pcr
+
(
G
)]
≥
4
E
[
m
]
−
18
E
[
n
]. Plugging in the expected values we get
2
6
3
7
m
3
m
3
1
34
.
2
that pcr
+
(
G
)
≥
≥
n
2
.
n
2
References
1. Ackerman, E.: On topological graphs with at most four crossings per edge
(manuscript)
2. Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar
graphs. J. Combinatorial Theory, Ser. A 114(3), 563-571 (2007)
3. Aigner, M., Ziegler, G.: Proofs from the Book. Springer, Heidelberg (2004)
4. Ajtai, M., Chvatal, V., Newborn, M., Szemeredi, E.: Crossing-free subgraphs. In:
Theory and Practice of Combinatorics. North-Holland Math. Stud., vol. 60, pp.
9-12. North-Holland, Amsterdam (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 Shue-
Exchange Graph and Other Networks. MIT Press, Cambridge (1983)
7. Matoussek, J.: Near-optimal separators in string graphs, ArXiv (February 2013)
8. Montaron, B.: An improvement of the crossing number bound. J. Graph The-
ory 50(1), 43-54 (2005)
9. Pach, J., Radoici´c,R.,Tardos,G.,Toth, G.: Improving the crossing lemma by
finding more crossings in sparse graphs. Disc. Compu. Geometry 36(4), 527-552
(2006)
10. Pach, J., Toth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3),
427-439 (1997)
11. Pach, J., Toth, G.: Thirteen problems on crossing numbers. Geombinatorics 9(4),
194-207 (2000)
12. Pach, J., Toth, G.: Which crossing number is it anyway? J. Combin. Theory Ser.
B 80(2), 225-246 (2000)
13. Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Removing independently even cross-
ings. SIAM J. on Disc. Math. 24(2), 379-393 (2010)
14. Schaefer, M.: The graph crossing number and its variants: A survey. Electronic
Journal of Combinatorics, Dynamic Survey 21 (2013)
15. Schaefer, M., Stefankovic, D.: Decidability of string graphs. J. Comput. System
Sci. 68(2), 319-334 (2004)
3
Here we need the restriction that there are no adjacent crossings: an adjacent crossing
would survive with probability
p
3
instead of
p
4
. This was overlooked in a preliminary
version of this paper when this theorem was stated for pcr instead of pcr
+
.
