Abstract
We consider classical linear-time planar separator algorithms, determining for a given planar graph a small subset of the nodes whose removal separates the graph into two components of similar size. These algorithms are based upon Planar Separator Theorems, which guarantee separators of size \(O(\sqrt{n})\) and remaining components of size less than 2n/3. In this work, we present a comprehensive experimental study of the algorithms applied to a large variety of graphs, where the main goal is to find separators that do not only satisfy upper bounds but also possess other desirable qualities with respect to separator size and component balance. We propose the usage of fundamental cycles, whose size is at most twice the diameter of the graph, as planar separators: For graphs of small diameter the guaranteed bound is better than the \(O(\sqrt{n})\) bounds, and it turns out that this simple strategy almost always outperforms the other algorithms, even for graphs with large diameter.
This work was partially supported by the IST Programme of EC under contract no. IST-2002-001907 (DELIS).
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
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 177–189 (1979)
Djidjev, H.N.: On the problem of partitioning planar graphs. SIAM Journal on Algebraic and Discrete Methods 3, 229–240 (1982)
Alon, N., Seymour, P., Thomas, R.: Planar separators. SIAM Journal on Discrete Mathematics 7, 184–193 (2004)
Djidjev, H.N., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta Informatica 34, 231–243 (1997)
Aleksandrov, L., Djidjev, H.N., Guo, H., Maheshwari, A.: Partitioning planar graphs with costs and weights. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol. 2409, pp. 98–110. Springer, Heidelberg (2002)
Holzer, M., Prasinos, G., Schulz, F., Wagner, D., Zaroliagis, C.: Engineering planar separator algorithms. Technical Report 2005-20, Fakultät Informatik, Universität Karlsruhe, TH (2005), http://www.ubka.uni-karlsruhe.de/vvv/ira/2005/20/20.pdf
Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM 46, 787–832 (1999)
Mehlhorn, K.: Data Structures and Algorithms 1, 2, and 3. Springer, Heidelberg (1984)
Kozen, D.: The Design and Analysis of Algorithms. Springer, Heidelberg (1992)
Ashcraft, C., Liu, J.W.H.: Applications of the Dulmage-Mendelsohn decomposition and network flow to graph bisection improvement. Technical Report CS-96-05, Dept. of Computer Science, York University, North York, Ontario, Canada (1996), http://www.cs.yorku.ca/techreports/1996/CS-96-05.html
Bourke, P.: Sphere generation (1992), http://astronomy.swin.edu.au/~pbourke/modelling/sphere/
Näher, S., Mehlhorn, K.: The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999), http://www.algorithmic-solutions.com
Diekmann, R.: (Graph Partitioning Graph Collection), http://wwwcs.upb.de/fachbereich/AG/monien/RESEARCH/PART/graphs.html
BARD (Bay Area Regional Database), http://bard.wr.usgs.gov
ESRI (Environmental Systems Research Institute), http://www.esri.com
Karypis, G.: (MeTiS), http://www-users.cs.umn.edu/~karypis/metis
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Holzer, M., Prasinos, G., Schulz, F., Wagner, D., Zaroliagis, C. (2005). Engineering Planar Separator Algorithms. In: Brodal, G.S., Leonardi, S. (eds) Algorithms – ESA 2005. ESA 2005. Lecture Notes in Computer Science, vol 3669. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561071_56
Download citation
DOI: https://doi.org/10.1007/11561071_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29118-3
Online ISBN: 978-3-540-31951-1
eBook Packages: Computer ScienceComputer Science (R0)