Disjoint Edges in Topological Graphs and the Tangled-Thrackle Conjecture

Ruis-Vargas, Andres J. and Suk, Andrew and Tóth, Csaba D. (2014) Disjoint Edges in Topological Graphs and the Tangled-Thrackle Conjecture. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 284-293 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_24).

Full text not available from this repository.


It is shown that for a constant t ∈ ℕ, every simple topological graph on n vertices has O(n) edges if the graph has no two sets of t edges such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is K t,t -free). As an application, we settle the tangled-thrackle conjecture formulated by Pach, Radoičić, and Tóth: Every n-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most O(n) edges.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_24
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
M Methods > M.100 Algebraic
Z Theory > Z.999 Others
ID Code:1440

Repository Staff Only: item control page


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

Fulek, R., Pach, J.: A computational approach to Conway’s thrackle conjecture. Computational Geometry: Theory and Applications 44, 345–355 (2011)

Fulek, R., Ruiz-Vargas, A.J.: Topological graphs: empty triangles and disjoint matchings. In: Proc. Symposium on Computational Geometry, pp. 259–266. ACM Press (2013)

Lovász, L., Pach, J., Szegedy, M.: On Convway’s trackle conjecture. Discrete & Compuational Geometry 18, 369–376 (1998)

Matousek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer (2002)

Nivasch, G.: Improved bounds and new techniques for Davenport–Schinzel sequences and their generalizations. JACM 57(3), article 17 (2010)

Pach, J.: Geometric graph theory. In: Goodman, J., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., ch. 10. CRC Press, Boca Rotan (2007)

Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley, New York (1995)

Pach, J., Radoičić, R., Tóth, G.: Tangled thrackles. In: Márquez, A., Ramos, P., Urrutia, J. (eds.) EGC 2011. LNCS, vol. 7579, pp. 45–53. Springer, Heidelberg (2012)

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)

Pach, J., Sterling, E.: Conway’s conjecture for monotone thrackles. American Mathematical Monthly 118(6), 544–548 (2011)

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

Pettie, S.: Sharp bounds on Davenport-Schinzel sequences of every order. In: Proc. Symposium

on Computational Geometry, pp. 319–328. ACM Press (2013)

Sharir, M., Agarwal, P.K.: Devenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press (1995)

Suk, A.: Density theorems for intersection graphs of t-monotone curves. SIAM Journal on Discrete Mathematics 27, 1323–1334 (2013)

Suk, A.: Disjonit edges in complete toplogical graphs. Discrete & Computational Geometry 49, 280–286 (2013)