Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 450))
Included in the following conference series:
262Accesses
Abstract
In this paper we show that every 2-connected embedded planar graph with faces of sizesd1.....df has a simple cycle separator of size 1.58\(\sqrt {d_1^2 + \cdots + d_f^2 }\)and we give an almost linear time algorithm for finding these separators,O(no(n,n)). We show that the new upper bound expressed as a function of ‖G‖=\(\sqrt {d_1^2 + \cdots + d_f^2 }\)is no larger, up to a constant factor than previous bounds that where expressed in terms of\(\sqrt {d \cdot v}\)whered is the maximum face size andν is the number of vertices and is much smaller for many graphs. The algorithms developed are simpler than earlier algorithms in that they work directly with the planar graph and its dual. They need not construct or work with the face-incidence graph as in [Mil86, GM87, GM].
This work was supported in part by grant number N00014-88-K-0623
This work was supported in part by National Science Foundation grant DCR-8713489.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Aho, J. Hopcroft, and J. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
K. Diks, H. N. Djidjev, O. Sykora, and I. Vrto. Edge separators for planar graphs and their applications. In Borlin, editor,Proc. of 13th Mathematical Foundation of Computer Science, pages 280–290, Carlsbad. Springer Verlage. LNCS 324.
H. N. Djidjev. A separator theorem.Compt. End Acad. Bulg. Sci., 34(5):643–645, 1981.
S. Even.Graph Algorithms. Computer Science Press, Potomac, Maryland, 1979.
Hillel Gazit. An improved algorithm for separating a planar graph. manuscript, 1986.
Hillel Gazit and Gary L. Miller. AnO(√n logn) optimal parallel algorithm for a separator for planar graphs. manuscript.
Hillel Gazit and Gary L. Miller. A parallel algorithm for finding a separator in planar graphs. In28th Annual Symposium on Foundations of Computer Science, pages 238–248, Los Angeles, October 1987. IEEE.
R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection.SIAM J. on Numerical Analysis, 16:346–358, 1979.
R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs.SIAM J. of Appl. Math., 36:177–189, April 1979.
Gary L. Miller. Finding small simple cycle separators for 2-connected planar graphs.Journal of Computer and System Sciences, 32(3):265–279, June 1986. invited publication.
Victor Pan and John Reif. Efficient parallel solution of linear systems. InProceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 143–152, Providence,RI, May 1985. ACM.
Author information
Authors and Affiliations
Department of Computer Science, Duke University, USA
Hillel Gazit
School of Computer Science Carnegie Mellon University & Dept of Computer Science, University of Southern California, USA
Gary L. Miller
- Hillel Gazit
You can also search for this author inPubMed Google Scholar
- Gary L. Miller
You can also search for this author inPubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gazit, H., Miller, G.L. (1990). Planar separators and the Euclidean norm. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_83
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-52921-7
Online ISBN:978-3-540-47177-6
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative