Depth-First Search and Kuratowski Subgraphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Depth-First Search and Kuratowski Subgraphs

Full text

Pdf (629 KB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 4 (October 1984) table of contents

Pages: 681 - 693

Year of Publication: 1984

ISSN:0004-5411

Author

S. G. Williamson

Department of Mathematics, University of California, San Diego, La Jolla, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 44, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1634.322451 What is a DOI?

REFERENCES

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	DICK, W. E., Vo, K. P., AND WILLIAMSON, S. G.Ranking and unranking planar embeddings. Lin. Multilin. Algebra, to appear.
	2	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]
	3	TARIAN, R. Depth first search and linear graph algorithms. SlAM J. Comput. I, 2, 146-159.
	4	WILLIAMSON, S.G. Embedding graphs in the plane-algorithmic aspects. Ann. Discrete Math 6 (1980), 349-384.
	5	WILLIAMSON, S. G. Finding a Kumtowski subgraph in linear time. Tech. Rep. 89/P-47. Univ. Louis Pasteur, IRMA, Strasbourg, France, 1980.

CITED BY 8

	André Kézdy , Patrick McGuinness, Sequential and parallel algorithms to find a K5 minor, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.345-356, September 1992, Orlando, Florida, United States
	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
	Erik D. Demaine , Mohammad Taghi Hajiaghayi , Naomi Nishimura , Prabhakar Ragde , Dimitrios M. Thilikos, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of Computer and System Sciences, v.69 n.2, p.166-166, September 2004
	John Boyer , Wendy Myrvold, Stop minding your p's and q's: a simplified O(n) planar embedding algorithm, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.140-146, January 17-19, 1999, Baltimore, Maryland, United States
	Ken-ichi Kawarabayashi , Bojan Mohar, Graph and map isomorphism and all polyhedral embeddings in linear time, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	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
	Zdeněk Dvořák , Ken-ichi Kawarabayashi , Robin Thomas, Three-coloring triangle-free planar graphs in linear time, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1176-1182, January 04-06, 2009, New York, New York
	Ken-ichi Kawarabayashi , Bruce Reed, Hadwiger's conjecture is decidable, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA