Cited By
View all- Zhang YPapamanthou CKatz J(2018)Verifiable Graph ProcessingACM Transactions on Privacy and Security10.1145/323318121:4(1-23)Online publication date: 1-Oct-2018
Short and Simple Cycle Separators in Planar Graphs
Authors: 
Eli Fox-Epstein, 
Shay Mozes, Phitchaya Mangpo Phothilimthana, Christian SommerAuthors Info & Claims
Article No.: 2.2, Pages 1 - 24
Abstract
We provide an implementation of an algorithm that, given a triangulated planar graph with m edges, returns a simple cycle that is a 3/4-balanced separator consisting of at most √8m edges. An efficient construction of a short and balanced separator that forms a simple cycle is essential in numerous planar graph algorithms, for example, for computing shortest paths, minimum cuts, or maximum flows. To the best of our knowledge, this is the first implementation of such a cycle separator algorithm with a worst-case guarantee on the cycle length.
We evaluate the performance of our algorithm and compare it to the planar separator algorithms recently studied by Holzer et al. [2009]. Out of these algorithms, only the Fundamental Cycle Separator (FCS) produces a simple cycle separator. However, FCS does not provide a worst-case size guarantee. We demonstrate that (1) our algorithm is competitive across all test cases in terms of running time, balance, and cycle length; (2) it provides worst-case guarantees on the cycle length, significantly outperforming FCS on some instances; and (3) it scales to large graphs.
References
[1]
Lyudmil Aleksandrov, Hristo Djidjev, Hua Guo, and Anil Maheshwari. 2007. Partitioning planar graphs with costs and weights. ACM Journal of Experimental Algorithmics 11, Article 1.5 (Feb. 2007). Announced at ALENEX 2002.
[2]
Lyudmil Aleksandrov and Hristo N. Djidjev. 1996. Linear algorithms for partitioning embedded graphs of bounded genus. SIAM Journal on Discrete Mathematics 9, 1 (1996), 129--150.
[3]
Noga Alon, Paul D. Seymour, and Robin Thomas. 1990. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3, 4 (1990), 801--808. Announced at STOC 1990.
[4]
Punyashloka Biswal, James R. Lee, and Satish Rao. 2010. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. Journal of the ACM 57, 3 (2010), 13:1--13:23. Announced at FOCS 2008.
[5]
Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. 2011. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. In 52nd IEEE Symposium on Foundations of Computer Science (FOCS’11). 170--179.
[6]
Sergio Cabello. 2012. Many distances in planar graphs. Algorithmica 62, 1--2 (2012), 361--381. Announced at SODA 2006.
[7]
Camil Demetrescu, Andrew V. Goldberg, and David Johnson. 2006. 9th DIMACS Implementation Challenge—Shortest Paths. (2006). http://www.dis.uniroma1.it/challenge9/download.shtml; accessed October 21, 2012.
[8]
Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson. 2008. Implementation challenge for shortest paths. In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.). Springer-Verlag New York.
[9]
Ralf Diekmann and Robert Preis. 1998. (1998). http://www2.cs.uni-paderborn.de/fachbereich/AG/monien/RESEARCH/PART/GRAPHS/FEM2.tar; accessed October 21, 2012.
[10]
Hristo N. Djidjev. 1982. On the problem of partitioning planar graphs. SIAM Journal on Algebraic Discrete Methods 3, 2 (1982), 229--240.
[11]
Hristo N. Djidjev. 1985. A linear algorithm for partitioning graphs of fixed genus. Serdica. Bulgariacae Mathematicae Publicationes 11, 4 (1985), 369--387. Announced in Comptes Rendus de l’Académie Bulgare des Sciences, 34:643--645, 1981.
[12]
Hristo N. Djidjev and Shankar M. Venkatesan. 1997. Reduced constants for simple cycle graph separation. Acta Informatica 34 (1997), 231--243.
[13]
Jittat Fakcharoenphol and Satish Rao. 2006. Planar graphs, negative weight edges, shortest paths, and near linear time. Journal of Computer and System Sciences 72, 5 (2006), 868--889. Announced at FOCS 2001.
[14]
Lamis M. Farrag. 1998. Applications of Graph Partitioning Algorithms to Terrain Visibility and Shortest Path Problems. Master’s thesis. School of Computer Science, Carleton University.
[15]
Eli Fox-Epstein, Shay Mozes, Phitchaya M. Phothilimthana, and Christian Sommer. 2013. Short and simple cycle separators in planar graphs. In Proceedings of the Meeting on Algorithm Engineering & Expermiments. Society for Industrial and Applied Mathematics, 26--40.
[16]
Greg N. Frederickson. 1987. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing 16, 6 (1987), 1004--1022.
[17]
Hillel Gazit and Gary L. Miller. 1990. Planar separators and the Euclidean norm. In SIGAL International Symposium on Algorithms. 338--347.
[18]
John R. Gilbert, Joan P. Hutchinson, and Robert E. Tarjan. 1984. A separator theorem for graphs of bounded genus. Journal of Algorithms 5, 3 (1984), 391--407. Announced as TR82-506 in 1982.
[19]
Michael T. Goodrich. 1995. Planar separators and parallel polygon triangulation. Journal of Computer and System Sciences 51, 3 (1995), 374--389. Announced at STOC 1992.
[20]
Monika R. Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 1 (1997), 3--23. Announced at STOC 1994.
[21]
Martin Holzer, Frank Schulz, Dorothea Wagner, Grigorios Prasinos, and Christos D. Zaroliagis. 2009. Engineering planar separator algorithms. ACM Journal of Experimental Algorithmics 14 (2009), 5:1.5--5:1.31.
[22]
Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. 2011. Improved algorithms for min cut and max flow in undirected planar graphs. In 43rd ACM Symposium on Theory of Computing (STOC’11). 313--322.
[23]
Ken-ichi Kawarabayashi, Philip N. Klein, and Christian Sommer. 2011. Linear-space approximate distance oracles for planar, bounded-genus, and minor-free graphs. In 38th International Colloquium on Automata, Languages and Programming (ICALP’11). 135--146.
[24]
Ken-ichi Kawarabayashi and Bruce A. Reed. 2010. A separator theorem in minor-closed classes. In 51st IEEE Symposium on Foundations of Computer Science (FOCS’10). 153--162.
[25]
Jonathan A. Kelner. 2006. Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. SIAM Journal on Computing 35, 4 (2006), 882--902. Announced at STOC 2004.
[26]
Philip N. Klein and Shay Mozes. 2013. Optimization Algorithms for Planar Graphs. http://www.planarity.org. (Forthcoming). Accessed April 2013.
[27]
Philip N. Klein, Shay Mozes, and Christian Sommer. 2013. Structured recursive separator decompositions for planar graphs in linear time. In 45th ACM Symposium on Theory of Computing (STOC’13). 505--514.
[28]
Philip N. Klein and Sairam Subramanian. 1998. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 22, 3 (1998), 235--249. Announced at WADS 1993.
[29]
Richard J. Lipton and Robert E. Tarjan. 1979. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 2 (1979), 177--189.
[30]
Richard J. Lipton and Robert E. Tarjan. 1980. Applications of a planar separator theorem. SIAM Journal on Computing 9, 3 (1980), 615--627. Announced at FOCS 1977.
[31]
Jakub Łącki and Piotr Sankowski. 2011. Min-cuts and shortest cycles in planar graphs in O(n log log n) time. In 19th European Symposium on Algorithms (ESA’11). 155--166.
[32]
Gary L. Miller. 1986. Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences 32, 3 (1986), 265--279.
[33]
Shay Mozes and Christian Sommer. 2012. Exact distance oracles for planar graphs. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 209--222.
[34]
Shay Mozes and Christian Wulff-Nilsen. 2010. Shortest paths in planar graphs with real lengths in O(nlog 2n/log log n) time. In 18th Annual European Symposium on Algorithms (ESA’10).
[35]
Serge A. Plotkin, Satish Rao, and Warren D. Smith. 1994. Shallow excluded minors and improved graph decompositions. In 5th ACM-SIAM Symposium on Discrete Algorithms (SODA’94). 462--470.
[36]
Bruce A. Reed and David R. Wood. 2009. A linear-time algorithm to find a separator in a graph excluding a minor. ACM Transactions on Algorithms 5, 4 (2009), 39:1--39:16. Announced at EuroComb 2005.
[37]
Daniel A. Spielman and Shang-Hua Teng. 1996. Disk packings and planar separators. In 12th Symposium on Computational Geometry (SoCG’96). 349--358.
[38]
Robert E. Tarjan. 1975. Efficiency of a good but not linear set union algorithm. Journal of the ACM 22, 2 (April 1975), 215--225.
[39]
Peter Ungar. 1951. A theorem on planar graphs. Journal of the London Mathematical Society s1-26, 4 (1951), 256--262.
[40]
Freek van Walderveen, Norbert Zeh, and Lars Arge. 2013. Multiway simple cycle separators and I/O-efficient algorithms for planar graphs. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA’13). ACM, 901--918.
[41]
Karl G. C. von Staudt. 1847. Geometrie der Lage. Bauer und Raspe, Nürnberg.
[42]
Hassler Whitney. 1932. Non-separable and planar graphs. Transactions of the American Mathematical Society 34, 2 (1932), 339--362.
[43]
Christian Wulff-Nilsen. 2011. Separator theorems for minor-free and shallow minor-free graphs with applications. In 52nd IEEE Symposium on Foundations of Computer Science (FOCS’11). 37--46.
Index Terms
- Short and Simple Cycle Separators in Planar Graphs
Recommendations
On ( 3 , 1 ) * -choosability of planar graphs without adjacent short cycles
A list assignment of a graph G is a function L that assigns a list L ( v ) of colors to each vertex v V ( G ) . An ( L , d ) -coloring is a mapping π that assigns a color π ( v ) L ( v ) to each vertex v V ( G ) so that at most d neighbors of v receive ...
Total domination in planar graphs of diameter two
MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...
On acyclic 4-choosability of planar graphs without short cycles
Let G=(V,E) be a graph. A proper vertex coloring of G is acyclic if G contains no bicolored cycle. Namely, every cycle of G must be colored with at least three colors. G is acyclicallyL-list colorable if for a given list assignment L={L(v):v@?V}, there ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 15 September 2016
Accepted: 01 June 2016
Revised: 01 May 2016
Received: 01 April 2013
Published in JEA Volume 21
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- Swiss National Science Foundation
- Israeli Science Foundation
- National Science Foundation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 289Total Downloads
- Downloads (Last 12 months)65
- Downloads (Last 6 weeks)15
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View all- Zhang YPapamanthou CKatz J(2018)Verifiable Graph ProcessingACM Transactions on Privacy and Security10.1145/323318121:4(1-23)Online publication date: 1-Oct-2018
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in