Density Theorems for Intersection Graphs of t-Monotone Curves

Suk, Andrew (2013) Density Theorems for Intersection Graphs of t-Monotone Curves. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 352-363 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_32).

Full text not available from this repository.

Abstract

A curve γ in the plane is t-monotone if its interior has at most $t − 1$ vertical tangent points. A family of t-monotone curves F is simple if any two members intersect at most once. It is shown that if F is a simple family of n t-monotone curves with at least $εn^2$ intersecting pairs (disjoint pairs), then there exists two subfamilies $F_1 , F_2 ⊂ F$ of size δn each, such that every curve in $F_1$ intersects (is disjoint to) every curve in $F_2$, where δ depends only on ε. We apply these results to find pairwise disjoint edges in simple topological graphs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_32
Classifications:P Styles > P.300 Curved
Z Theory > Z.500 Representations
Z Theory > Z.750 Topology
ID Code:1324

Repository Staff Only: item control page

References

Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. Theory Appl. 11, 209–218 (1998)

Alon, N., Pach, J., Pinchasi, R., Radoicic, R., Sharir, M.: Crossing patterns of semi-algebraic sets. J. Comb. Theory Ser. A 111, 310–326 (2005)

Asano, T., Imai, H.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4, 310–323 (1983)

Asplund, E., Grünbaum, B.: On a coloring problem. Math. Scand. 8, 181–188 (1960)

Basu, S.: Combinatorial complexity in o-minimal geometry. Proc. London Math. Soc. 100, 405–428 (2010)

Cairns, G., Nikolayevsky, Y.: Bounds for generalized thrackles. Discrete Comput. Geom. 23, 191–206 (2000)

Ehrlich, G., Even, S., Tarjan, R.E.: Intersection graphs of curves in the plane. J. Combinatorial Theory, Ser. B 21, 8–20 (1979)

Erdős, P., Hajnal, A.: Ramsey-type theorems. Discrete Appl. Math. 25, 37–52 (1989)

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

Fox, J., Sudakov, B.: Density theorems for bipartite graphs and related Ramsey-type results. Combinatorica 29, 153–196 (2009)

Fulek, R., Pach, J.: A computational approach to Conway’s thrackle conjecture. Comput. Geom. 44, 345–355 (2011)

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)

Gyárfás, A.: On the chromatic number of multiple intervals graphs and overlap graphs. Discrete Math. 55, 161–166 (1985)

Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130–136 (1985)

Kozik, J., Krawczyk, T., Lasoń, M., Micek, P., Pawlik, A., Trotter, W., Walczak, B.: Triangle-free intersection graphs of segments in the plane with arbitrarily large chromatic number (submitted)

Lovász, L., Pach, J., Szegedy, M.: On Conway’s thrackle conjecture. Discrete Comput. Geom. 18, 369–376 (1997)

Matoušek, J.: Lectures on Discrete Geometry. Springer, New York (2002)

Pach, J., Solymosi, J.: Crossing patterns of segments. J. Comb. Theory Ser. A 96, 316–325 (2001)

Pach, J., Sterling, E.: Conway’s conjecture for monotone thrackles. Amer. Math. Monthley 118, 544–548 (2011)

Pach, J., Töröcsik, J.: Some geometric applications of Dilworth’s theorem. Discrete Comput. Geom. 12, 1–7 (1994)

Pach, J., Tóth, G.: Which crossing number is it anyway? J. Comb. Theory Ser. B 80, 225–246 (2000)

Pach, J., Tóth, G.: Disjoint Edges in Topological Graphs. In: Akiyama, J., Baskoro, E.T., Kano, M. (eds.) IJCCGGT 2003. LNCS, vol. 3330, pp. 133–140. Springer, Heidelberg (2005)

Suk, A.: Coloring intersection graphs of x-monotone curves in the plane (submitted)

Suk, A.: Disjoint edges in complete topological graphs (to appear)

Tóth, G.: Note on geometric graphs. J. Comb. Theory Ser. A 89, 126–132 (2000)