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, Vienna, Austria , pp. 247-260 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_20).

Full text not available from this repository.

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

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
ID Code:513

Repository Staff Only: item control page

References

S. Benzer, On the topology of the genetic fine structure, Proceedings of the National Academy of Sciences of the United States of America 45 (1959), 1607-1620.

Z.-Z. Chen, M. Grigni, and C. H. Papadimitriou, Planar map graphs, in: STOC '98, ACM, 1998, 514-523.

Z.-Z. Chen, M. Grigni, and C. H. Papadimitriou, Planar topological inference, (Japanese) in: Algorithms and Theory of Computing (Kyoto, 1998) Surikaisekikenkyusho Kokyuroku 1041 (1998), 1-8.

Z.-Z. Chen, X. He, and M.-Y. Kao, Nonplanar topological inference and political-map graphs, in: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 1999), ACM, New York, 1999, 195-204.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

M. Egenhofer, A model for detailed binary topological relationships, Geomatica 47 (1993), 261-273.

M. Egenhofer and R. Franzosa, Point-set topological spatial relations, International Journal of Geographical Information Systems 5 (1991), 161-174.

M. Egenhofer and J. Sharma, Assessing the consistency of complete and incomplete topological information. Geographical Systems 1 (1993), 47-68.

G. Ehrlich, S. Even, and R. E. Tarjan, Intersection graphs of curves in the plane, Journal of Combinatorial Theory, Series B 21 (1976), 8-20.

P. Erdös, A. Hajnal and J. Pach. A Ramsey-type theorem for bipartite graphs, Geombinatorics 10 (2000), 64-68.

S. Even, A. Pnueli, and A. Lempel, Permutation graphs and transitive graphs, Journal of Association for Computing Machinery 19 (1972), 400-411.

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

R. L. Graham, Problem, in: Combinatorics, Vol. II (A. Hajnal and V. T. Sós, eds), North-Holland Publishing Company, Amsterdam, 1978, 1195.

J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21 (1974), 549-568.

J. Kratochvíl, String graphs, in: Graphs and Other Combinatorial Topics (Prague, 1982), Teubner-Texte Math. 59, Teubner, Leipzig, 1983, 168-172.

J. Kratochvíl, String graphs I: The number of critical nonstring graphs is infinite, Journal of Combinatorial Theory, Series B 52 (1991), 53-66.

J. Kratochvíl, String graphs II: Recognizing string graphs is NP-hard, Journal of Combinatorial Theory, Series B 52 (1991), 67-78.

J. Kratochvíl, Crossing number of abstract topological graphs, in: Graph drawing (Montreal, QC, 1998), Lecture Notes in Comput. Sci. 1547, Springer, Berlin, 1998, 238-245.

J. Kratochvíl, A. Lubiw, and J. Nesetril. Noncrossing subgraphs of topological layouts, SIAM J. Discrete Math. 4 (1991), 223-244.

J. Kratochvíl, J. Matousek. NP-hardness results for intersection graphs. Comment. Math. Univ. Carolin. 30 (1989), 761-773.

J. Kratochvíl, J. Matousek. String graphs requiringexponential representations. J. Combin. Theory Ser. B 53 (1991), 1-4.

Kratochvíl, J., Matousek, J.: Intersection graphs of segments, J. Combin. Theory Ser. B 62 (1994), 289-315.

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica 15 (1995), 215-245.

M. Middendorf and F. Pfeiffer. Weakly transitive orientations, Hasse diagrams and string graphs. In Graph Theory and Combinatorics (Marseille-Luminy, 1990), Discrete Math. 111 (1993), 393-400.

J. Pach and J. Solymosi, Crossing patterns of segments, Journal of Combinatorial Theory, Ser. A, to appear.

S. Rao. Small distortion and volume preserving embeddings for planar and euclidean metrics. In. Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), ACM, New York, 1999, 300-306.

M. Schaefer and D. Stefankovic, Decidability of string graphs, the 33rd Annual Symposium on the Theory of Computing '01, to appear.

F. W. Sinden, Topology of thin film RC circuits, Bell System Technological Journal (1966), 1639-1662.

T. R. Smith and K. K. Park, Algebraic approach to spatial reasoning, International Journal of Geographical Information Systems 6 (1992), 177-192.