Graph and map isomorphism and all polyhedral embeddings in linear time

ABSTRACT

For every surface S (orientable or non-orientable), we give a linear time algorithm to test the graph isomorphism of two graphs, one of which admits an embedding of face-width at least 3 into S. This improves a previously known algorithm whose time complexity is n^O(g), where g is the genus of S. This is the first algorithm for which the degree of polynomial in the time complexity does not depend on g. The above result is based on two linear time algorithms, each of which solves a problem that is of independent interest. The first of these problems is the following one. Let S be a fixed surface. Given a graph G and an integer k ≥ 3, we want to find an embedding of G in S of face-width at least k, or conclude that such an embedding does not exist. It is known that this problem is NP-hard when the surface is not fixed. Moreover, if there is an embedding, the algorithm can give all embeddings of face-width at least k, up to Whitney equivalence. Here, the face-width of an embedded graph G is the minimum number of points of G in which some non-contractible closed curve in the surface intersects the graph. In the proof of the above algorithm, we give a simpler proof and a better bound for the theorem by Mohar and Robertson concerning the number of polyhedral embeddings of 3-connected graphs. The second ingredient is a linear time algorithm for map isomorphism and Whitney equivalence. This part generalizes the seminal result of Hopcroft and Wong that graph isomorphism can be decided in linear time for planar graphs.

REFERENCES

• 1: Isolde Adler , Martin Grohe , Stephan Kreutzer, Computing excluded minors, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.641-650, January 20-22, 2008, San Francisco, California
• 2: Dan Archdeacon, Densely embedded graphs, Journal of Combinatorial Theory Series B, v.54 n.1, p.13-36, Jan. 1992 [doi>10.1016/0095-8956(92)90064-5]
• 3: Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
• 4: L. Babai, Monte Carlo algorithms in graph isomorphism testing, Univ. Montreal Tech. Rep. DMS 79-10, 1979. http://people.cs.uchicago.edu/laci/lasvegas79.pdf
• 5: L. Babai, P. Erdos, and S. Selkow, Random graph i-isomorphism, SIAM J. Computing 9,628--635, (1980).
• 6: László Babai , D. Yu. Grigoryev , David M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.310-324, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802206]
• 7: Laszlo Babai , Ludik Kucera, Canonical labelling of graphs in linear average time, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), p.39-46, October 29-31, 1979
• 8: László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
• 9: Hans L. Boblaender, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, Journal of Algorithms, v.11 n.4, p.631-643, Dec. 1990 [doi>10.1016/0196-6774(90)90013-5]
• 10: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 11: C. Paul Bonnington , M. J. Grannell , T. S. Griggs , J. Širáň, Exponential families of non-isomorphic triangulations of complete graphs, Journal of Combinatorial Theory Series B, v.78 n.2, p.169-184, March 2000 [doi>10.1006/jctb.1999.1939]
• 12: K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graphplanarity using PQ-trees, J. Comput. System Sci. 13(1976), 335--379.
• 13: R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
• 14: T. Brahana, Systems of circuits on 2-dimensional manifolds, Ann. Math. 23 (1921), 144--168.
• 15: Sergio Cabello , Bojan Mohar, Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs, Discrete & Computational Geometry, v.37 n.2, p.213-235, February 2007 [doi>10.1007/s00454-006-1292-5]
• 16: Jianer Chen, A Linear-Time Algorithm for Isomorphism of Graphs of Bounded Average Genus, SIAM Journal on Discrete Mathematics, v.7 n.4, p.614-631, Nov. 1994 [doi>10.1137/S0895480191196769]
• 17: Jianer Chen, Algorithmic graph embeddings, Theoretical Computer Science, v.181 n.2, p.247-266, July 30, 1997 [doi>10.1016/S0304-3975(96)00273-3]
• 18: Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, Journal of Computer and System Sciences, v.30 n.1, p.54-76, Feb. 1985 [doi>10.1016/0022-0000(85)90004-2]
• 19: Hristo Djidjev , John Reif, An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.337-347, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103456]
• 20: R. Diestel, Graph Theory, 3rd Edition, Springer, 2005.
• 21: Reinhard Diestel , Tommy R. Jensen , Konstantin Yu. Gorbunov , Carsten Thomassen, Highly connected sets and the excluded grid theorem, Journal of Combinatorial Theory Series B, v.75 n.1, p.61-73, Jan. 1999 [doi>10.1006/jctb.1998.1862]
• 22: Jeff Erickson , Sariel Har-Peled, Optimally cutting a surface into a disk, Proceedings of the eighteenth annual symposium on Computational geometry, p.244-253, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513430]
• 23: I. S. Filotti , Gary L. Miller , John Reif, On determining the genus of a graph in O(v O(g)) steps(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.27-37, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804395]
• 24: I. S. Filotti , Jack N. Mayer, A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.236-243, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804671]
• 25: John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
• 26: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 27: S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
• 28: Martin Grohe, Isomorphism testing for embeddable graphs through definability, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.63-72, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335313]
• 29: M. Grohe and O. Verbitsky, Testing graph isomorphism in parallel by playing a game, In 33rd International Colloquium on Automata, Languages and Programming(ICALP), 2006, 3--14.
• 30: J. E. Hopcroft , J. K. Wong, Linear time algorithm for isomorphism of planar graphs (Preliminary Report), Proceedings of the sixth annual ACM symposium on Theory of computing, p.172-184, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803896]
• 31: J. E. Hopcroft and R. Tarjan, Dividing a graph into triconnected components, Siam J. Comput. 2 (1973), 135--158.
• 32: J. E. Hopcroft and R. Tarjan, Isomorphism of planar graphs (working paper), In R. E. Miller and J.W. Thathcer, editors, Complexity of Computer Computations.Plenum Press, 1972.
• 33: J. E. Hopcroft and R. Tarjan, A v łog v algorithm for isomorphism of triconnected planargraphs, J. Comp. Syst. Sci. 7 (1973), 323--331.
• 34: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 35: M. Juvan, J. Marinček, and B. Mohar, Elimination of local bridges, Math. Slovaca 47 (1997),85--92.
• 36: Ken-Ichi Kawarabayashi , Bojan Mohar, Some Recent Progress and Applications in Graph Minor Theory, Graphs and Combinatorics, v.23 n.1, p.1-46, February 2007 [doi>10.1007/s00373-006-0684-x]
• 37: Ken-ichi Kawarabayashi , Buce Reed, Computing crossing number in linear time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250848]
• 38: K. Kawarabayashi, B. Mohar, and B. Reed, A simpler linear time algorithm for embedding graphs into anarbitrary surface, in preparation.
• 39: Francis Lazarus , Michel Pocchiola , Gert Vegter , Anne Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, Proceedings of the seventeenth annual symposium on Computational geometry, p.80-89, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378630]
• 40: David Lichtenstein, Isomorphism for graphs embeddable on the projective plane, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.218-224, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804669]
• 41: R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, Siam J. Appl. Math. 36 (1979), 177--189.
• 42: R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem, Siam J. Comput. 9 (1980), 615--627.
• 43: E. Luks, Isomorphism of graphs of bounded valance can be tested in polynomialtime, J. Computer and System Sciences 25, 42--65,(1982).
• 44: G. Miller, Isomorphism of graphs which are pairwise k-separable, Information and Control 56, 21--33, (1983).
• 45: G. Miller, Isomorphism of k-contractible graphs. A generalization of boundedvalence and bounded genus graphs, Information and Control 56, 1--20, (1983).
• 46: Gary Miller, Isomorphism testing for graphs of bounded genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.225-235, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804670]
• 47: B. Mohar, Uniqueness and minimality of large face-width embeddings of graphs, Combinatorica 15 (1995), 541--556.
• 48: Bojan Mohar, Embedding graphs in an arbitrary surface in linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.392-397, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237986]
• 49: Bojan Mohar, A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface, SIAM Journal on Discrete Mathematics, v.12 n.1, p.6-26, Jan. 1999 [doi>10.1137/S089548019529248X]
• 50: B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395--401.
• 51: Bojan Mohar , Neil Robertson, Flexibility of polyhedral embeddings of graphs in surfaces, Journal of Combinatorial Theory Series B, v.83 n.1, p.38-57, September 2001 [doi>10.1006/jctb.2001.2036]
• 52: B. Mohar and C. Thomassen, Graphs on Surfaces, Johns HopkinsUniversity Press, Baltimore, MD, 2001.
• 53: I. N. Ponomarenko, The isomorphism problem for classes of graphs that are invariantwith respect to contraction, Zap. Nauchen. Sem. Leningrad.Osdel. Mat. Inst. Steklov. (LOMI) 174, 147--177, (1988), inRussian.
• 54: I. N. Ponomarenko, The isomorphism problem for classes of graphs, Dokl. Akad. Nauk SSSR 304 (1989) 552--556;Engl. transl. in Soviet Math. Dokl. 39 (1989) 119--122.
• 55: B. Reed, Tree width and tangles: a new connectivity measure and someapplications, in "Surveys in Combinatorics, 1997 (London)", London Math. Soc. Lecture Note Ser. 241, Cambridge Univ. Press, Cambridge, 1997, pp. 87--162.
• 56: B. Reed, N. Robertson, A. Schrijver and P. D. Seymour,Finding disjoint trees in planar graphs in linear time, in Graph Structure Theory (Seattle, WA, 1991), 295--301,%Contemp. Math. 147,Amer. Math. Soc., 1993.
• 57: Bruce Reed, Rooted routing in the plane, Discrete Applied Mathematics, v.57 n.2-3, p.213-227, Feb. 24, 1995 [doi>10.1016/0166-218X(94)00104-L]
• 58: Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
• 59: Neil Robertson , P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, Journal of Combinatorial Theory Series B, v.45 n.2, p.212-254, Oct. 1988 [doi>10.1016/0095-8956(88)90070-6]
• 60: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
• 61: Neil Robertson , P. D. Seymour, Graph minors. XVI. excluding a non-planar graph, Journal of Combinatorial Theory Series B, v.89 n.1, p.43-76, September 2003 [doi>10.1016/S0095-8956(03)00042-X]
• 62: Neil Robertson , P. D. Seymour, Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory Series B, v.92 n.2, p.325-357, November 2004 [doi>10.1016/j.jctb.2004.08.001]
• 63: Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073]
• 64: N. Robertson, R. P. Vitray, Representativity of surface embeddings,in: "Paths, Flows, and VLSI-Layout,"B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver Eds.,Springer-Verlag, Berlin, 1990, pp. 293--328.
• 65: Uwe Schöning, Graph isomorphism is in the low hierarchy, Journal of Computer and System Sciences, v.37 n.3, p.312-323, Dec. 1988 [doi>10.1016/0022-0000(88)90010-4]
• 66: P. D. Seymour , Robin Thomas, Uniqueness of highly representative surface embeddings, Journal of Graph Theory, v.23 n.4, p.337-349, Dec. 1996 [doi>10.1002/(SICI)1097-0118(199612)23:4<337::AID-JGT2>3.0.CO;2-S]
• 67: C. Thomassen, The graph genus problem is NP-complete, Journal of Algorithms, v.10 n.4, p.568-576, Dec. 1989 [doi>10.1016/0196-6774(89)90006-0]
• 68: Carsten Thomassen, Triangulating a surface with a prescribed graph, Journal of Combinatorial Theory Series B, v.57 n.2, p.196-206, March 1993 [doi>10.1006/jctb.1993.1016]
• 69: Carsten Thomassen, A simpler proof of the excluded minor theorem for higher surfaces, Journal of Combinatorial Theory Series B, v.70 n.2, p.306-311, July 1997 [doi>10.1006/jctb.1997.1761]
• 70: Gert Vegter , Chee K. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry, p.102-111, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98546]
• 71: H. Weinberg, A simple and efficient algorithm fordetermining isomorphism of planar triply connected graphs, Circuit Theory 13 (1966), 142--148.
• 72: S. G. Williamson, Depth-First Search and Kuratowski Subgraphs, Journal of the ACM (JACM), v.31 n.4, p.681-693, Oct. 1984 [doi>10.1145/1634.322451]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
graph isomorphism, linear time algorithm, map isomorphism