k-Quasi-Planar Graphs

Suk, Andrew (2012) k-Quasi-Planar Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 266-277 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_26).

Full text not available from this repository.

Abstract

A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A topological graph is simple if every pair of its edges intersect at most once (either at a vertex or at their intersection). In 1996, Pach, Shahrokhi, and Szegedy [16] showed that every n-vertex simple k-quasi-planar graph contains at most O (n(log n)hoch 2k−4) edges. This upper bound was recently improved (for large k) by Fox and Pach [8] to n(log n)O(log k). In this note, we show that all such graphs contain at most n(log2n)2α ck(n) edges, where α(n) denotes the inverse Ackermann function and ck is a constant that depends only on k.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_26
Classifications:M Methods > M.600 Planar
ID Code:1261

Repository Staff Only: item control page

References

Ackerman, E.: On the Maximum Number of Edges in Topological Graphs with No Four Pairwise Crossing Edges. In: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, SCG 2006, pp. 259–263. ACM, New York (2006)

Ackerman, E., Fox, J., Pach, J., Suk, A.: On Grids in Topological Graphs. In: Proceedings of the 25th Annual Symposium on Computational Geometry, SCG 2009, pp. 403–412. ACM, New York (2009)

Ackerman, E., Tardos, G.: Note: On the Maximum Number of Edges in Quasi-Planar Graphs. J. Comb. Theory Ser. A 114(3), 563–571 (2007)

Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-Planar Graphs Have a Linear Number of Edges. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 1–7. Springer, Heidelberg (1995)

Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, Berlin (2005)

Capoyleas, V., Pach, J.: A Turán-Type Theorem on Chords of a Convex Polygon. J. Combinatorial Theory, Series B 56, 9–15 (1992)

Dilworth, R.P.: A decomposition theorem for partially ordered sets. Annals of Math 51, 161–166 (1950)

Fox, J., Pach, J.: Coloring Kk -Free Intersection Graphs of Geometric Objects in the Plane. In: Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry, SCG 2008, pp. 346–354. ACM, New York (2008)

Fox, J., Pach, J., Tóth, C.: Intersection Patterns of Curves. Journal of the London Mathematical Society 83, 389–406 (2011)

Fulek, R., Suk, A.: Disjoint Crossing Families. In: EuroComb 2011 (2011, to appear)

Klazar, M.: A General Upper Bound in Extremal Theory of Sequences. Commentationes Mathematicae Universitatis Carolinae 33(4), 737–746 (1992)

Klazar, M., Valtr, P.: Generalized Davenport-Schinzel Sequences. Combinatorica 14, 463–476 (1994)

Nivasch, G.: Improved Bounds and New Techniques for Davenport–Schinzel Sequences and Their Generalizations. J. ACM 57(3), 3, Article 17 (2010)

Pach, J., Radoičić, R., Tóth, G.: Relaxing Planarity for Topological Graphs. In: Akiyama, J., Kano, M. (eds.) JCDCG 2002. LNCS, vol. 2866, pp. 221–232. Springer, Heidelberg (2003)

Pach, J., Pinchasi, R., Sharir, M., Tóth, G.: Topological Graphs with No Large Grids. Graph. Comb. 21(3), 355–364 (2005)

Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the Crossing Number. J. Graph Theory 22, 239–243 (1996)

Pettie, S.: Generalized Davenport-Schinzel Sequences and Their 0-1 Matrix Counterparts. J. Comb. Theory Ser. A 118(6), 1863–1895 (2011)

Pettie, S.: On the Structure and Composition of Forbidden Sequences, with Geometric Applications. In: Proceedings of the 27th Annual ACM Symposium on Computational Geometry, SCG 2011, pp. 370–379. ACM, New York (2011)

Tardos, G., Tóth, G.: Crossing Stars in Topological Graphs. SIAM J. Discret. Math. 21(3), 737–749 (2007)

Valtr, P.: On Geometric Graphs with No k Pairwise Parallel Edges. Discrete Comput. Geom. 19(3), 461–469 (1997)

Valtr, P.: Graph Drawings with No k Pairwise Crossing Edges. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 205–218. Springer, Heidelberg (1997)