Embedding graphs in an arbitrary surface in linear time

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	D. Archdeacon, The complexity of the graph embedding problem, in "Topics in Combinatorics and Graph Theory," R. Bodendiek and R. Henn (Eds.), Physica- Verlag, Heidelberg, 1990, pp. 59-64.
	2	Dan Archdeacon , Phil Huneke, A Kuratowski theorem for nonorientable surfaces, Journal of Combinatorial Theory Series B, v.46 n.2, p.173-231, April 1989 [doi>10.1016/0095-8956(89)90043-9]
	3	J. Battle, F. Harary, Y. Kodama, J. W. T. Youngs, Additivity of the genus of a graph, Bull. Amer. Math. Soc. 68 (1962) 565-568.
	4	K. S. Booth, G. S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-trees, J. Comput. System Sci. 13 (1976) 335- 379.
	5	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]
	6	S. A. Cook, R. A. Reckhow, Time bounded random access machines, J. Comput. Syst. Sci. 7 (1976) 354- 375.
	7	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]
	8	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]
	9	Jonathan L. Gross , Thomas W. Tucker, Topological graph theory, Wiley-Interscience, New York, NY, 1987
	10	J. E. Hopcroft, P~. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2 (1973) 135-158.
	11	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]
	12	M. Juvan, J. MaxinSoek, B. Mohar, Elimination of local bridges, Math. Slovaca, to appear.
	13	M. Juvan, J. Marin~ek, B. Mohar, Obstructions for simple embeddings, preprint, 1994.
	14	M. Juvan, J. Maxin~:ek, B. Mohax, Embedding a graph into the torus in linear time, preprint, 1994.
	15	M. Juvan, B. Mohar, Extending 2-restricted partial embeddings of graphs, preprint, 1995.
	16	A. Karabeg, Classification and detection of obstructions to planarity, Lin. Multilin. Algebra 26 (1990) 15- 38.
	17	Bojan Mohar, Projective planarity in linear time, Journal of Algorithms, v.15 n.3, p.482-502, Nov. 1993 [doi>10.1006/jagm.1993.1050]
	18	B. Mohar, Obstructions for the disk and the cylinder embedding extension problems, Combin. Probab. Cornput. 3 (1994) 375-406.
	19	B. Mohar, Universal obstructions for embedding extension problems, preprint, 1994.
	20	B. Mohar, C. Thomassen, Graphs on surfaces.
	21	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]
	22	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]
	23	N. Robertson, P. D. Seymour, Graph minors. XXI. Graphs with unique linkages, preprint, 1992.
	24	N. Robertson, P. D. Seymour, Graph minors. XXII. Irrelevant vertices in linkage problems, preprint, 1992.
	25	N. Robertson, P. D. Seymour, An outline of a disjoint paths algorithm, in: "Paths, Flows, and VLSI-Layout" (B. Korte, L. Lov~sz, H. J. Pr5mel and A. Schrijver eds.), Springer-Verlag, Berlin, 1990, pp. 267--292.
	26	P. D. Seymour, A bound on the excluded minors for a surface, submitted.
	27	S. Stahl, L. W. Beineke, Blocks and the nonorientable genus of graphs, j. Graph Theory i (1977) 75-78.
	28	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]
	29	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]
	30	S. G. Williamson, Embedding graphs in the plane algorithmic aspects, Ann. Discrete Math. 6 (1980) 349- 384.
	31	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]