Recognizing String Graphs Is Decidable

Pach, János and Tóth, Géza (2002) Recognizing String Graphs Is Decidable. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001 , pp. 247-260(Official URL:

Full text not available from this repository.


A graph is called a string graph if its vertices can be represented by continuous curves ("strings") in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function $f(n)$ with the property that every string graph of $n$ vertices has a representation in which any two curves cross at most $f(n)$ times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).

Item Type: Conference Paper
Additional Information: 10.1007/3-540-45848-4_20
Classifications: Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.999 Others

Actions (login required)

View Item View Item