Algorithms for simple curves on surfaces, string graphs, and crossing numbers

We consider algorithmic problems for simple curves on a surface M with non-empty boundary. The surface M is given by a triangulation T such that all vertices of T are on the boundary ∂M. The isotopy class of a simple curve is given by normal coordinates---a sequence of intersection numbers of a with the edges of T.; The GEOMETRIC INTERSECTION NUMBER problem is to determine the minimal number of intersections of two curves achievable by deforming the curves. The DEHN-T WIST problem is to compute the Dehn-twist of a simple curve along another closed simple curve. We give the first polynomial-time algorithm for DEHN-TWIST and, as a consequence, for G EOMETRIC INTERSECTION NUMBER, in the compressed representation. The previous algorithms only allowed computing Dehn-twists along a specific set of simple closed curves.; The STRING GRAPH problem asks if a graph can be realized as an intersection graph of a set of curves in the plane, that is, whether there exists a collection of curves, one for each vertex, such that two curves intersect if and only if the corresponding vertices are adjacent. The decidability of the STRING GRAPH problem was open for over thirty years. We will first show that the problem is in NEXP, and then, using algorithms for simple curves on surfaces, we will further decrease the complexity to NP, completely resolving the status of the STRING GRAPH problem which turns out to be NP-complete.; The crossing number of a graph G is the minimum number of intersections in a drawing of G in the plane. The odd crossing number of a graph G is the minimum number of pairs of edges that cross odd number of times in a drawing of G. Hanani and Tutte showed that if the odd crossing number is zero then the crossing number is zero as well. Pach and Toth asked whether the numbers are the same for all graphs. Our study of the intersection numbers has lead us to an infinite sequence of graphs for which the ratio of the odd crossing number and the crossing number approaches 3 /2.