Recognizing string graphs in NP

ABSTRACT

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.

REFERENCES

• 1: S. Benzer. On the topology of the genetic fine structure. Proceedings of the National Academy of Science, 45:1607--1620, 1959.
• 2: Zhi-Zhong Chen , Enory Grigni , Christos H. Papadimitriou, Planar map graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.514-523, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276865]
• 3: Volker Diekert , Claudio Gutiérrez , Christian Hagenah, The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.170-182, February 15-17, 2001
• 4: Volker Diekert , Yuri Matiyasevich , Anca Muscholl, Solving Trace Equations Using Lexicographical Normal Forms, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.336-346, July 07-11, 1997
• 5: Volker Diekert , Anca Muscholl, Solvability of Equations in Free Partially Commutative Groups Is Decidable, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.543-554, July 08-12, 2001
• 6: B. Farb and B. Thurston. Homeomorphisms and simple closed curves. unpublished manuscript, 1991.
• 7: M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4(3):312--316, 1983.
• 8: Leszek Gasieniec , Marek Karpinski , Wojciech Plandowski , Wojciech Rytter, Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract), Proceedings of the 5th Scandinavian Workshop on Algorithm Theory, p.392-403, July 03-05, 1996
• 9: R. L. Graham. Problem 1. In Open Problems at 5th Hungarian Colloquium on Combinatorics, 1976.
• 10: M. Grigni, D. Papadias, and C. Papadimitriou. Topological inference. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, pages 901--906, 1995.
• 11: Jan Kratochvíl, String graphs. I.: the number of critical nonstring graphs is infinite, Journal of Combinatorial Theory Series B, v.52 n.1, p.53-66, May 1991 [doi>10.1016/0095-8956(91)90090-7]
• 12: Jan Kratochvíl, String graphs. II.: Recognizing string graphs is NP-hard, Journal of Combinatorial Theory Series B, v.52 n.1, p.67-78, May 1991 [doi>10.1016/0095-8956(91)90091-W]
• 13: Jan Kratochvíl, Crossing Number of Abstract Topological Graphs, Proceedings of the 6th International Symposium on Graph Drawing, p.238-245, August 01, 1998
• 14: Jan Kratochvíl , Jiří Matoušek, String graphs requiring exponential representations, Journal of Combinatorial Theory Series B, v.53 n.1, p.1-4, Sept. 1991 [doi>10.1016/0095-8956(91)90050-T]
• 15: M. Lothaire. Algebraic combinatorics on words. To be published by Campbridge University Press, 2002.
• 16: J. Matoušek, J. Nešetřil, and R. Thomas. On polynomial time decidability of induced-minor-closed classes. Comment. (MATH). Univ. Carolin., 29(4):703--710, 1988.
• 17: János Pach , Géza Tóth, Which crossing number is it anyway?, Journal of Combinatorial Theory Series B, v.80 n.2, p.225-246, Nov. 2000 [doi>10.1006/jctb.2000.1978]
• 18: János Pach , Géza Tóth, Recognizing String Graphs Is Decidable, Revised Papers from the 9th International Symposium on Graph Drawing, p.247-260, September 23-26, 2001
• 19: Wojciech Plandowski , Wojciech Rytter, Application of Lempel-Ziv Encodings to the Solution of Words Equations, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.731-742, July 13-17, 1998
• 20: Marcus Schaefer , Daniel Stefankovic, Decidability of string graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.241-246, July 2001, Hersonissos, Greece [doi>10.1145/380752.380807]
• 21: F. W. Sinden. Topology of thin film circuits. Bell System Technical Journal, 45:1639--1662, 1966.
• 22: Mikkel Thorup, Map Graphs In Polynomial Time, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.396, November 08-11, 1998

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Line and curve generation
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Experimentation, Performance, Theory