Paper Info
Title
Decidability of string graphs
Abstract
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}).
Year
DOI
Venue
2001
10.1145/380752.380807
STOC
Keywords
Field
DocType
finite fields,upper bound
Discrete mathematics,Combinatorics,Finite field,Exponential function,Open problem,Nondeterministic algorithm,Upper and lower bounds,Decidability,String graph,Conjecture,Mathematics
Conference
ISBN
Citations 
PageRank 
1-58113-349-9
22
2.30
References 
Authors
17
2
Name
Order
Citations
PageRank
Marcus Schaefer112312.63
Daniel Stefankovic224328.65