A Computational Approach to Conway's Thrackle Conjecture

A drawing of a graph in the plane is called a thrackle if every pair of edges meets precisely once, either at a common vertex or at a proper crossing. Let t(n) denote the maximum number of edges that a thrackle of n vertices can have. According to a 40 years old conjecture of Conway, t(n) = n for every n >= 3. For any epsilon > 0, we give an algorithm terminating in e(O)((1/epsilon(2))ln(1/epsilon)) steps to decide whether t(n) = 3. Using this approach, we improve the best known upper bound, t(n) 3.(n 1), due to Cairns and Nikolayevsky, to 167/117n< 10428n. (C) 2011 Elsevier B.V. All rights reserved.

A computational approach to Conway's thrackle conjecture

Radoslav Fulek, János Pach

2011

Intersection Patterns of Edges in Topological Graphs

Radoslav Fulek

This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossing. Conway's Thrackle Conjecture says that a thrackle cannot have more edges than vertices. By a computational approach we improve the previously known upper bound of 1.5n on the maximal number of edges in a thrackle with n vertices to 1.428n. Moreover, our method yields an algorithm with a finite running time that for any ε > 0 either verifies the upper bound of (1 + ε)n on the maximum number of edges in a thrackle or disproves the conjecture. It is not hard to see that any simple graph admits a poly-line drawing in the plane such that each edge is represented by a polygonal curve with at most three bends, and each edge crossings realizes a prescribed angle α. We show that if we restrict the number of bends per edge to two and allow edges to cross in k different angles, a graph on n vertices admitting such a drawing can have at most O(nk2) edges. This generalizes a previous result of Arikushi et al., in which the authors treated a special case of our problem, where k = 1 and the prescribed angle has 90 degrees. The classical result known as Hanani-Tutte Theorem states that a graph is planar if and only if it admits a drawing in the plane in which each pair of non-adjacent edges crosses an even number of times. We prove the following monotone variant of this result, conjectured by J.Pach and G.Tóth. If G has an x-monotone drawing in which every pair of independent edges crosses evenly, then G has an x-monotone embedding (i.e. a drawing without crossings) with the same vertex locations. We show several interesting algorithmic consequences of this result. In a drawing of a graph, two edges form an odd pair if they cross each other an odd number of times. A pair of edges is independent (or non-adjacent) if they share no endpoint. For a graph G we let ocr(G) be the smallest number of odd pairs in a drawing of G and let iocr(G) be the smallest number of independent odd pairs in a drawing of G. We construct a graph G with iocr(G) < ocr(G), answering a question by Székely, and –for the first time– giving evidence that crossings of adjacent edges may not always be trivial to eliminate.

EPFL2012

Intersection Patterns of Edges in Topological Graphs

Radoslav Fulek

EPFL2012