Disjoint Edges in Topological Graphs and the Tangled-Thrackle Conjecture

Ruiz-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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1440

Actions (login required)

View Item View Item