Disjoint Edges in Topological Graphs and the TangledThrackle ConjectureRuisVargas, Andres J. and Suk, Andrew and Tóth, Csaba D. (2014) Disjoint Edges in Topological Graphs and the TangledThrackle Conjecture. In: Graph Drawing 22nd International Symposium, GD 2014, September 2426, 2014 , pp. 284293(Official URL: http://dx.doi.org/10.1007/9783662458037_24). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_24
AbstractIt 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 tangledthrackle conjecture formulated by Pach, Radoičić, and Tóth: Every nvertex 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.
Actions (login required)
