A Pseudo-Approximation for the Genus of Hamiltonian Graphs

by Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos

Theory of Computing, Volume 13(5), pp. 1-47, 2017

Bibliography with links to cited articles

[1]   Chandra Chekuri and Anastasios Sidiropoulos: Approximation algorithms for Euler genus and related problems. In Proc. 54th FOCS, pp. 167–176. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.26, arXiv:1304.2416]

[2]   Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky: A note on approximating graph genus. Inform. Process. Lett., 61(6):317–322, 1997. [doi:10.1016/S0020-0190(97)00203-2]

[3]   Ion S. Filotti, Gary L. Miller, and John H. Reif: On determining the genus of a graph in O(vO(g)) steps. In Proc. 11th STOC, pp. 27–37. ACM Press, 1979. [doi:10.1145/800135.804395]

[4]   Jonathan L. Gross and Thomas W. Tucker: Topological Graph Theory. Courier Corporation, 1987.

[5]   Allen Hatcher: Algebraic Topology. Cambridge Univ. Press, 2002. Available at the author’s webpage.

[6]   John E. Hopcroft and Robert Endre Tarjan: Efficient planarity testing. J. ACM, 21(4):549–568, 1974. [doi:10.1145/321850.321852]

[7]   Ken-ichi Kawarabayashi, Bojan Mohar, and Bruce A. Reed: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In Proc. 49th FOCS, pp. 771–780. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.53]

[8]   Ken-ichi Kawarabayashi and Anastasios Sidiropoulos: Beyond the Euler characteristic: Approximating the genus of general graphs. In Proc. 47th STOC, pp. 675–682. ACM Press, 2015. [doi:10.1145/2746539.2746583, arXiv:1412.1792]

[9]   Yury Makarychev, Amir Nayyeri, and Anastasios Sidiropoulos: A pseudo-approximation for the genus of Hamiltonian graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 244–259. Springer, 2013. [doi:10.1007/978-3-642-40328-6_18]

[10]   Aleksander Malnič and Bojan Mohar: Generating locally cyclic triangulations of surfaces. J. Combin. Theory Ser. B, 56(2):147–164, 1992. [doi:10.1016/0095-8956(92)90015-P]

[11]   Bojan Mohar: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math., 12(1):6–26, 1999. Preliminary version in STOC’96. [doi:10.1137/S089548019529248X]

[12]   Bojan Mohar: Face covers and the genus problem for apex graphs. J. Combin. Theory Ser. B, 82(1):102–117, 2001. [doi:10.1006/jctb.2000.2026]

[13]   Bojan Mohar and Carsten Thomassen: Graphs on Surfaces. John Hopkins Univ. Press, 2001.

[14]   Neil Robertson and Paul D. Seymour: Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Combin. Theory Ser. B, 48(2):255–288, 1990. [doi:10.1016/0095-8956(90)90121-F]

[15]   Carsten Thomassen: The graph genus problem is NP-complete. J. Algorithms, 10(4):568–576, 1989. [doi:10.1016/0196-6774(89)90006-0]

[16]   Carsten Thomassen: Triangulating a surface with a prescribed graph. J. Combin. Theory Ser. B, 57(2):196–206, 1993. [doi:10.1006/jctb.1993.1016]

[17]   Arthur T. White: Graphs of Groups on Surfaces: Interactions and Models. Volume 188. Elsevier, 2001.