Disk packings and planar separators

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Disk packings and planar separators

Full text

Pdf (870 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twelfth annual symposium on Computational geometry table of contents

Philadelphia, Pennsylvania, United States

Pages: 349 - 358

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Daniel A. Spielman	Computer Science Division, U.C. Berkeley, CA
Shang-Hua Teng	Department of Computer Science, University of Minnesota, Minneapolis, MN

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 34, Citation Count: 6

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/237218.237404 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	Noga Alon , Paul Seymour , Robin Thomas, Planar Separators, SIAM Journal on Discrete Mathematics, v.7 n.2, p.184-193, May 1994 [doi>10.1137/S0895480191198768]
	2	E. M. Andreev. On convex polyhedra in Lobacevskii space. Math. USSR Sbornik, 10(3):413-440, 1970.
	3	E. M. Andreev. On convex polyhedra of finite volume in Lobacevskii space. Math. USSR $bornik, 12(2):270-259, 1970.
	4	J. Pach and P. Agarwal. Combinatorial Geometry. Wiley-Interscience, 1995.
	5	F. Cao, J. R. Gilbert, and S.-H. Teng. Partitioning Unstructured Meshes with Lines and Planes. the 9th International Conference on Domain Decomposition, submitted, 1996.
	6	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 [doi>10.1145/160985.161004]
	7	H. N. Djidjev. On the problem of partitioning planar graphs. SIAM J. Alg. Disc. Math, 3(2): 229-240, June, 1982.
	8	H. N. Djidjev. Personal communication, 1995, citing H. N. Djidjev and S. M. Venkatesan, Reduced constants for simple cycle graph separation, Acta Informatica (to appear).
	9	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	10	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 [doi>10.1145/160985.161005]
	11	I. Fgry. On straight line representation of planar graphs. Acta. Sci. Math. 11: 229-233, 1948.
	12	Hubert de Fraysseix , János Pach , Richard Pollack, Small sets supporting fary embeddings of planar graphs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.426-433, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62254]
	13	Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
	14	H. Gazit. An Improved Algorithm for Separating a Planar Graph, manuscript, USC, 1986.
	15	Hillel Gazit , Gary L. Miller, Planar separators and the Euclidean norm, Proceedings of the international symposium on Algorithms, p.338-347, August 1990, Tokyo, Japan
	16	G. Hardy, J. E. Littlewood, and G. P61ya. Inequalities. Cambridge University Press, second edition, 1952.
	17	P. Koebe. Kontaktprobleme der konformen Abbildung. Bey. Verb. SSchs. Akademie der Wissenschaften Leipzig, Math.-Phys. Klasse, 88:141- 164, 1936.
	18	R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. of Appl. Math., 36:177-189, April 1979.
	19	R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM J. on Numerical Analysis, 16:346-358, 1979.
	20	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]
	21	Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
	22	Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Geometric Separators for Finite-Element Meshes, SIAM Journal on Scientific Computing, v.19 n.2, p.364-386, March 1998 [doi>10.1137/S1064827594262613]
	23	G. L. Miller , W. Thurston, Separators in two and three dimensions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.300-309, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100255]
	24	Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
	25	C. Thomassen. Planarity and duality of finite and infinite graphs. Journal of Combinatorial Theory, Series B, 29: 244-271, 1980.
	26	W. P. Thurston. The geometry and topology of 3-manifolds. Princeton University Notes, 1988.
	27	W. T. Tutte. Convex representations of graphs. Proc. London Math. Soc. 10(3): 304-320, 1960.
	28	W. T. Tutte. How to draw a graph. Proc. London Math. Soc. 13(3): 743-768, 1963.

CITED BY 6

	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
	David Eppstein, Dynamic generators of topologically embedded graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Jochen Alber , Henning Fernau , Rolf Niedermeier, Graph separators: a parameterized view, Journal of Computer and System Sciences, v.67 n.4, p.808-832, December 2003
	Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000
	David Eppstein , Michael T. Goodrich , Darren Strash, Linear-time algorithms for geometric graphs with sublinearly many crossings, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.150-159, January 04-06, 2009, New York, New York
	David Eppstein , Michael T. Goodrich, Studying (non-planar) road networks through an algorithmic lens, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California