NDLI: I/O-Efficient Planar Separators

Please wait, while we are loading the content...

I/O-Efficient Planar Separators

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Zeh, Norbert Maheshwari, Anil
Copyright Year	2008
Abstract	We present I/O-efficient algorithms for computing optimal separator partitions of planar graphs. Our main result shows that, given a planar graph G with N vertices and an integer $r > 0$, a vertex separator of size O$(N / \sqrt{r})$ that partitions G into O$(N / r)$ subgraphs of size at most r and boundary size O$(\sqrt{r})$ can be computed in O$(\operatorname{sort}(N))$ I/Os. This bound holds provided that $M \ge 56r \log^2 B$. Together with an I/O-efficient planar embedding algorithm presented in [N. Zeh, I/O-Efficient Algorithms for Shortest Path Related Problems, Ph.D. thesis, School of Computer Science, Carleton University, Ottawa, ON, Canada, 2002], this result is the basis for I/O-efficient solutions to many other fundamental problems on planar graphs, including breadth-first search and shortest paths [L. Arge, G. S. Brodal, and L. Toma, J. Algorithms, 53 (2004), pp. 186206; L. Arge, L. Toma, and N. Zeh, I/O-efficient algorithms for planar digraphs, in Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2003, pp. 8593], depth-first search [L. Arge et al., J. Graph Algorithms Appl., 7 (2003), pp. 105129; L. Arge and N. Zeh, I/O-efficient strong connectivity and depth-first search for directed planar graphs, in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2003, pp. 261270], strong connectivity [L. Arge and N. Zeh, I/O-efficient strong connectivity and depth-first search for directed planar graphs, in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2003, pp. 261270], and topological sorting [L. Arge and L. Toma, Simplified external memory algorithms for planar DAGs, in Proceedings of the 9th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Comput. Sci. 3111, Springer-Verlag, Berlin, New York, 2004, pp. 493503; L. Arge, L. Toma, and N. Zeh, I/O-efficient algorithms for planar digraphs, in Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2003, pp. 8593]. Our second result shows that, given I/O-efficient solutions to these problems, a general separator algorithm for graphs with costs and weights on their vertices [L. Aleksandrov et al., Partitioning planar graphs with costs and weights, in Proceedings of the 4th Workshop on Algorithm Engineering and Experiments, Lecture Notes in Comput. Sci. 2409, Springer-Verlag, Berlin, New York, 2002, pp. 98107] can be made I/O-efficient. Many classical separator theorems are special cases of this result. In particular, our I/O-efficient version allows the computation of a separator as produced by our first separator algorithm, but without placing any constraints on r in relation to the memory size.
Starting Page	767
Ending Page	801
Page Count	35
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539705446925
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	38
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2008-05-28
Access Restriction	Subscribed
Subject Keyword	Analysis of algorithms and problem complexity planar graphs graph separators Decomposition methods memory hierarchies I/O-efficient algorithms graph algorithms Programming involving graphs or networks Large-scale problems
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Quick k-Median, k-Center, and Facility Location for Sparse Graphs

Partitioning Planar Graphs

The Vertex-Disjoint Menger Problem in Planar Graphs

Coordination in Coarse-Grained Decomposition

Pebbling in Split Graphs

Multicoordination Methods for Solving Convex Block-Angular Programs

Extremal metrics on graphs I

Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver

Homology Flows, Cohomology Cuts

I/O-Efficient Planar Separators

Similar Documents

Quick k-Median, k-Center, and Facility Location for Sparse Graphs

Partitioning Planar Graphs

The Vertex-Disjoint Menger Problem in Planar Graphs

Coordination in Coarse-Grained Decomposition

Pebbling in Split Graphs

Multicoordination Methods for Solving Convex Block-Angular Programs

Extremal metrics on graphs I

Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver

Homology Flows, Cohomology Cuts

I/O-Efficient Planar Separators