Marcus Schaefer 0001

STOC Conference 2002 Conference Paper

Recognizing string graphs in NP

• Marcus Schaefer 0001
• Eric Sedgwick
• Daniel Stefankovic

A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. We show that string graphs can be recognized in NP . The recognition problem was not known to be decidable until very recently, when two independent papers established exponential upper bounds on the number of intersections needed to realize a string graph [18, 20]. These results implied that the recognition problem lies in NEXP . In the present paper we improve this by showing that the recognition problem for string graphs is in NP , and therefore NP -complete, since Kratochvíl [12] showed that the recognition problem is NP -hard. The result has consequences for the computational complexity of problems in graph drawing, and topological inference.

STOC Conference 2001 Conference Paper

Decidability of string graphs

• Marcus Schaefer 0001
• Daniel Stefankovic

We show that string graphs can be recognized in nondeterministic exponential time by giving an exponential upper bound on the number of intersections for a drawing realizing the string graph in the plane. This upper bound confirms a conjecture by Kratochv\'{\i}l and Matou\v{s}ek~\cite{KM91} and settles the long-standing open problem of the decidability of string graph recognition (Sinden~\cite{S66}, Graham~\cite{G76}). Finally we show how to apply the result to solve another old open problem: deciding the existence of Euler diagrams, a central problem of topological inference (Grigni, Papadias, Papadimitriou~\cite{GPP95}).

STOC Conference 1999 Conference Paper

Graph Ramsey Theory and the Polynomial Hierarchy

• Marcus Schaefer 0001