An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alpert, S.R. The genera of amalgamations of graphs. Trans. Amer. Math. Soc., 178 (1973) 1-39.
	2	Alpert, S.R., and Gross J.L. Graph Imbedding Problems, in Research Problems (Richard Guy, ed.).
	3	Battle, J., Harary, F., Kodama, Y., and Youngs, J.W.T. "Additivity of the Genus of a Graph". Bull. Amer. Math. Soc. 68 (1962), 565- 568.
	4	E. A. Bender , L. B. Richmond, 3-edge-connected embeddings have few singular edges, Journal of Graph Theory, v.14 n.4, p.475-477, Sep. 1990 [doi>10.1002/jgt.3190140411]
	5	Djidjev, H.N., A linear algorithm for partitioning graphs of fixed genus, Serdiea Bulgaricae mathematicae publications, Vol 11, (1985), 369-387.
	6	Edmonds, J. A combinatorial representation for polyhedral surfaces. Not. Am. Math. Soc. 7 (1960), 646.
	7	M. R. Fellows , M. A. Langston, Nonconstructive advances in polynomial-time complexity, Information Processing Letters, v.26 n.3, p.155-162, Nov. 23, 1987
	8	Michael R. Fellows , Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM (JACM), v.35 n.3, p.727-739, July 1988 [doi>10.1145/44483.44491]
	9	Filotti, I.S. An algorithm for imbedding cubic graphs in the torus, J. Comput. Syst. Sci. 20 (1980), 255-276.
	10	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]
	11	Merrick L. Furst , Jonathan L. Gross , Lyle A. McGeoch, Finding a maximum-genus graph imbedding, Journal of the ACM (JACM), v.35 n.3, p.523-534, July 1988 [doi>10.1145/44483.44485]
	12	Jonathan L. Gross , Ronald H. Rosen, A Linear Time Planarity Algorithm for 2-Complexes, Journal of the ACM (JACM), v.26 n.4, p.611-617, Oct. 1979 [doi>10.1145/322154.322156]
	13	Jonathan L. Gross , Thomas W. Tucker, Topological graph theory, Wiley-Interscience, New York, NY, 1987
	14	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]
	15	Khuller, S., S.G. Mitchell, and V.V. Vazirani, "Processor efficient parallel algorithms for the two disjoint paths problem, and for f'mding a Kuratowski homeomorph", 30th Annual Symposium on Foundations of Computer Sceince", Durham, NC, Oct, 1989, p 300- 305
	16	Philip N. Klein , John H. Reif, An efficient parallel algorithm for planarity, Journal of Computer and System Sciences, v.37 n.2, p.190-246, October 1988 [doi>10.1016/0022-0000(88)90006-2]
	17	Kruskal, J. "Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture", Trans. Amer. Math. Soc. 95 (1960), 210-225.
	18	Kuratowski, "Sur le problem des courbes gauches en topologie", Fund. Math. 15 (1930), 271-283.
	19	Massey, W.S. Algebraic Topology: An Introduction, Harcourt, Brace, and World, New York, 1967.
	20	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]
	21	Gary L. Miller, Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus), Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.310-327, August 21-27, 1983
	22	ibid, "Isomorphism of k-contractible Graphs (a Generalization of Bounded Valence and Bounded Genus)". Information & Control 65, 1-2 (Jan/Feb 1983), 1-20.
	23	ibid, An Additivity Theorem for the Genus of a Graph, MIT, TR-85- 342.
	24	Rarnachandran, V. and J.H. Reif, An optimal parallel algorithm for planarity, 30th Annual Symposium on Foundations of Computer Sceince", Durham, NC, Oct 1989.
	25	Reif, J. On the Complexity of Extending Partial Imbeddings, Computer Science Dept, Univ Rochester, Technical Report TR33, Oct 1978.
	26	ibid, Polynomial Time Recognition of Graphs of Fixed Genus, Computer Science Dept, Univ Rochester, Technical Report TR33, Oct 1978.
	27	Robertson, N., and Seymour, P.D. "Graph minors. I. Excluding a forest", J. Combinatorial Theory (Ser. B), 39-61.
	28	ibid, "Graph minors. II. Algorithmic aspects of tree-width", J. Algorithms, 7 (1986), 309-322.
	29	ibid, "Graph minors. HI. Planar tree-width", J. Combinatorial Theory (Ser. B), 49-64.
	30	N. Robertson , P. D. Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, Journal of Combinatorial Theory Series B, v.48 n.2, p.227-254, Apr. 1990 [doi>10.1016/0095-8956(90)90120-O]
	31	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]
	32	Neil Robertson , P D Seymour, Graph minors. VI. Disjoint paths across a disc, Journal of Combinatorial Theory Series B, v.41 n.1, p.115-138, Aug. 1986 [doi>10.1016/0095-8956(86)90031-6]
	33	ibid, "Graph Minors. XII. Disjoint paths on a surface", preprint, Sept 1986
	34	N. Robertson , P. D. Seymour, Graph minors. VIII. A Kuratowski theorem for general surfaces, Journal of Combinatorial Theory Series B, v.48 n.2, p.255-288, Apr. 1990 [doi>10.1016/0095-8956(90)90121-F]
	35	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]
	36	ibid, "Graph Minors. XVI. Wagner's Conjecture", preprint, to appear
	37	ibid, "Graph Minors - a Survey", in Survcya in Combinatoricn (I. Anderson, ed.), Cambridge Univ. Press (1985), 153-171.
	38	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]
	39	Tutte, W.T. "Combinatorial Oriented Maps". Can. J. Math. 31, 5 (1979), 986-1004.
	40	Wagner, K. "Uber Einer Eigenshaft der Ebener Complexe", Math. Ann.14 (1937), 570-590.
	41	White, A.T. Graphs, Groups, and Surfaces, North-Holland, Amsterdam, 1973.
	42	Youngs, J.W.T. Minimal imbeddings and the genus of a graph, J. Math. Mech., 12 (1963) 303-315. MR 26 #3043.