Embedding and canonizing graphs of bounded genus in logspace. (English) Zbl 1315.68254
Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 383-392 (2014).
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C51 | Graph designs and isomorphic decomposition |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
Euler genus; algorithmic graph theory; computational complexity; graph embedding; isomorphism; logspaceSoftware:
SuLQReferences:
| [1] | I. Adler, M. Grohe, and S. Kreutzer. Computing excluded minors. In Proc. SODA 2008, pages 641-650. SIAM, 2008. · Zbl 1192.68810 |
| [2] | E. Allender and M. Mahajan. The complexity of planarity testing. Inf. Comp., 189(1):117-134, 2004. 10.1016/j.ic.2003.09.002 · Zbl 1072.68045 |
| [3] | E. Allender, D. Mix Barrington, T. Chakraborty, S. Datta, and S. Roy. Planar and grid graph reachability problems. TOCS, 45(4):675-723, 2009. 10.1007/s00224-009-9172-z · Zbl 1183.68409 |
| [4] | T. Böhme and B. Mohar. Labeled K2,t minors in plane graphs. J. of Combinatorial Theory, Series B, 84(2):291-300, 2002. 10.1006/jctb.2001.2083 · Zbl 1024.05082 |
| [5] | C. Bourke, R. Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM ToCT, 1(1):1-17, 2009. 10.1145/1490270.1490274 · Zbl 1322.68095 |
| [6] | S. Datta, A. Gopalan, R. Kulkarni, and R. Tewari. Improved bounds for bipartite matching on surfaces. In Proc. STACS 2012, volume 14 of LIPIcs, pages 254-265. Dagstuhl, 2012. · Zbl 1245.68102 |
| [7] | S. Datta, R. Kulkarni, R. Tewari, and N. V. Vinodchandran. Space complexity of perfect matching in bounded genus bipartite graphs. J. Comput. Syst. Sci., 78(3):765-779, 2012. 10.1016/j.jcss.2011.11.002 · Zbl 1253.68168 |
| [8] | S. Datta, N. Limaye, and P. Nimbhorkar. 3-connected planar graph isomorphism is in log-space. In Proc. FSTTCS 2008, volume 2 of LIPIcs, pages 155-162. Dagstuhl, 2008. · Zbl 1248.68213 |
| [9] | S. Datta, N. Limaye, P. Nimbhorkar, T. Thierauf, and F. Wagner. Planar graph isomorphism is in log-space. In Proc. CCC 2009, pages 203-214. IEEE, 2009. 10.1109/CCC.2009.16 |
| [10] | S. Datta and G. Prakriya. Planarity testing revisited. In Proc. TAMC 2011, volume 6648 of LNCS, pages 540-551. Springer, 2011. · Zbl 1331.68102 |
| [11] | R. Diestel. Graph Theory, volume 173. Springer, 3rd edition, 2005. · Zbl 1074.05001 |
| [12] | H. Djidjev and J. Reif. An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs. In Proc. STOC 1991, pages 337-347. ACM, 1991. 10.1145/103418.103456 |
| [13] | M. Elberfeld, A. Jakoby, and T. Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proc. FOCS 2010, pages 143-152. IEEE, 2010. 10.1109/FOCS.2010.21 |
| [14] | I. S. Filotti, G. L. Miller, and J. Reif. On determining the genus of a graph in O(v^O(g)) steps (preliminary report). In Proc. STOC 1979, pages 27-37. ACM, 1979. 10.1145/800135.804395 |
| [15] | M. Grohe. Isomorphism testing for embeddable graphs through definability. In Proc. STOC 2000, pages 63-72. ACM, 2000. 10.1145/335305.335313 · Zbl 1296.05134 |
| [16] | M. Grohe, K.-i. Kawarabayashi, and B. A. Reed. A simple algorithm for the graph minor decomposition – logic meets structural graph theory. In Proc. 2012, pages 414-431. SIAM, 2013. · Zbl 1423.05159 |
| [17] | L. A. Hemaspaandra and M. Ogihara. The complexity theory companion. Springer, 2002. · Zbl 0993.68042 |
| [18] | B. Jenner, J. Köbler, P. McKenzie, and J. Torán. Completeness results for graph isomorphism. J. Comput. Syst. Sci., 66(3):549-566, 2003. 10.1016/S0022-0000(03)00042-4 · Zbl 1054.68101 |
| [19] | K.-i. Kawarabayashi, B. Mohar, and B. Reed. A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In Proc. FOCS 2008, pages 771-780. IEEE, 2008. 10.1109/FOCS.2008.53 |
| [20] | M. Koucký. Universal traversal sequences with backtracking. JCSS, 65(4):717-726, 2002. 10.1016/S0022-0000(02)00023-5 · Zbl 1059.68080 |
| [21] | J. Kynčl and T. Vyskočil. Logspace reduction of directed reachability for bounded genus graphs to the planar case. ACM ToCT, 1(3):8:1-8:11, 2010. 10.1145/1714450.1714451 · Zbl 1322.68107 |
| [22] | S. Lindell. A logspace algorithm for tree canonization (extended abstract). In Proc. STOC 1992, pages 400-404. ACM, 1992. 10.1145/129712.129750 |
| [23] | M. Mahajan and K. R. Varadarajan. A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). In Proc. STOC 2000, pages 351-357. ACM, 2000. 10.1145/335305.335346 · Zbl 1296.05187 |
| [24] | A. Malnič and B. Mohar. Generating locally cyclic triangulations of surfaces. J. of Combinatorial Theory, Series B, 56(2):147-164, 1992. 10.1016/0095-8956(92)90015-P · Zbl 0723.05053 |
| [25] | B. Mohar. Combinatorial local planarity and the width of graph embeddings. Canadian J. of Mathematics, 44(6):1272-1288, 1992. · Zbl 0777.05052 |
| [26] | B. Mohar. Uniqueness and minimality of large face-width embeddings of graphs. Combinatorica, 15(4):541-556, 1995. · Zbl 0838.05041 |
| [27] | B. Mohar. A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discret. Math., 12(1):6-26, 1999. 10.1137/S089548019529248X · Zbl 0931.05025 |
| [28] | B. Mohar and C. Thomassen. Graphs on Surfaces. The Johns Hopkins University Press, 2001. · Zbl 0979.05002 |
| [29] | N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complement. Chicago J. Theor. Comput. Sci., 1995. · Zbl 0924.68039 |
| [30] | O. Reingold. Undirected connectivity in log-space. JACM, 55(4):1-24, 2008. 10.1145/1391289.1391291 · Zbl 1315.68156 |
| [31] | N. Robertson and P. Seymour. Graph minors. vii. disjoint paths on a surface. J. of Combinatorial Theory, Series B, 45(2):212-254, 1988. 10.1016/0095-8956(88)90070-6 · Zbl 0658.05044 |
| [32] | N. Robertson and P. Seymour. Graph minors. viii. a kuratowski theorem for general surfaces. J. of Combinatorial Theory, Series B, 48(2):255-288, 1990. 10.1016/0095-8956(90)90121-F · Zbl 0719.05033 |
| [33] | N. Robertson and R. Vitray. Representativity of surface embeddings. In Paths, Flows, and vlsi-layout, pages 293-328. Springer-Verlag, Berlin, 1990. · Zbl 0735.05032 |
| [34] | D. Stolee and N. V. Vinodchandran. Space-efficient algorithms for reachability in surface-embedded graphs. In Proc. CCC 2012, pages 326-333, 2012. 10.1109/CCC.2012.15 |
| [35] | C. Thomassen. The graph genus problem is NP-complete. J. of Algorithms, 10(4):568-576, 1989. 10.1016/0196-6774(89)90006-0 · Zbl 0689.68071 |
| [36] | C. Thomassen. Embeddings of graphs with no short noncontractible cycles. J. of Combinatorial Theory, Series B, 48(2):155-177, 1990. 10.1016/0095-8956(90)90115-G · Zbl 0704.05011 |
| [37] | C. Thomassen. A simpler proof of the excluded minor theorem for higher surfaces. J. of Combinatorial Theory, Series B, 70(2):306-311, 1997. 10.1006/jctb.1997.1761 · Zbl 0882.05053 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
