Recognizing String Graphs Is Decidable

Abstract. 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).