Separators in two and three dimensions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Separators in two and three dimensions

Full text

Pdf (803 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 300 - 309

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

G. L. Miller	School of Computer Science, Carnegie Mellon University & Dept of Computer Science, University of Southern California
W. Thurston	Dept of Mathematics, Princeton University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 36, 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/100216.100255 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.

	Bir59	B. J. Birch. On 3N points in a plane. Proc. Cambridge Philos. Soc., 55(4):289- 293, 1959.
	Dji82	H. N. Djidjev. On the problem of partitioning planar graphs. SIAM J. ALG. DISC. METH., 3(2):229-240, June 1982.
	Ede87	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	FJ86	Greg Fredrickson and Ravi Janardan. Separator-based strategies for efficient message routing. In 27th Annual Symposium on Foundations of Computer Science, pages 428-437. IEEE, Oct 1986.
	Gaz86	Hiilel Gazit. An improved algorithm for separating a planar graph, manuscript, 1986.
	GHT82	John R. Gilbert , Joan P. Hutchinson , Robert E Tarjan, A Separator Theorem for Graphs of Bounded Genus, Cornell University, Ithaca, NY, 1982
	Gib77	P. J. Giblin. Graphs, Surfaces and Homology. Mathematics Series. Chapman and Hall, 1977.
	GM	Hillel Gazit and Gary L. Miller. An O(logn) optimal parallel algorithm for a separator for planar graphs. manuscript.
	GM87	Hillel Gazit and Gary L. Miller. A parallel algorithm for finding a separator in planar graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 238-248, Los Angeles, October 1987. IEEE.
	GT87	J. R. Gilbert , R. E. Tarjan, The analysis of a nested dissection algorithm, Numerische Mathematik, v.50 n.4, p.377-404, FEB. 1987 [doi>10.1007/BF01396660]
	HM86	Joan P. Hutchinson and Gary L. Miller. On deleting vertices to make a graph of positive genus planar. In Discrete Algorithms and Complexity Theory - Proceedings of the Japan- US Joint Seminar, Kyoto, Japan, pages 81-98, Boston, 1986. Academic Press.
	HW87	David Haussler and Emo Welzl. E-nets and simplex range queries. Discrete and Computational Geometry, 2:127- 151, 1987.
	Lei83	Frank Thomson Leighton. Complexity Issues in VLSI. Foundations of Computing. MIT Press, Cambridge, MA, 1983.
	LRT79	R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM J. on Numerical Analysis, 16:346-358, 1979.
	LT79	R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. of Appl. Math., 36:177-189, April 1979.
	Mil86	Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
	MT90	Gary Miller and Shang Hua Teng. Centerpoints and point divsions. manuscript, 1990.
	PR85a	V Pan , J Reif, Efficient parallel solution of linear systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.143-152, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22161]
	PR85b	Victor Pan and John H. Reif. Extension of parallel nested dissection algorithm to the path algebra problems. Technical Report TR-85-9, Computer Science Department, State University of New York at Albany, New York, 1985.
	Tho80a	C. Thomassen. Planarity and duality of finite and infinite planar graphs. J. Combinatorial Theory, Series B, 29:244-271, 1980.
	Tho80b	Clark David Thompson, A complexity theory for vlsi, 1980
	VC71	V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Th. Prob. and its Appl., 16(2):264- 280, 1971.

CITED BY 9

	Serge Plotkin , Satish Rao , Warren D. Smith, Shallow excluded minors and improved graph decompositions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.462-470, January 23-25, 1994, Arlington, Virginia, United States
	David Eppstein , Gary L. Miller , Shang-Hua Teng, A deterministic linear time algorithm for geometric separators and its applications, Proceedings of the ninth annual symposium on Computational geometry, p.99-108, May 18-21, 1993, San Diego, California, United States
	Daniel A. Spielman , Shang-Hua Teng, Disk packings and planar separators, Proceedings of the twelfth annual symposium on Computational geometry, p.349-358, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Gary L. Miller , Stephen A. Vavasis, Density graphs and separators, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.331-336, January 28-30, 1991, San Francisco, California, United States
	Alan M. Frieze , Gary L. Miller , Shang-Hua Teng, Separator based parallel divide and conquer in computational geometry, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.420-429, June 29-July 01, 1992, San Diego, California, United States
	Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997
	K. L. Clarkson , David Eppstein , Gary L. Miller , Carl Sturtivant , Shang-Hua Teng, Approximating center points with iterated radon points, Proceedings of the ninth annual symposium on Computational geometry, p.91-98, May 18-21, 1993, San Diego, California, United States
	Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany
	Charles R. Collins , Kenneth Stephenson, A circle packing algorithm, Computational Geometry: Theory and Applications, v.25 n.3, p.233-256, July 2003