### Engineering planar separator algorithmsEngineering planar separator algorithms

Access Restriction
Subscribed

 Author Holzer, Martin ♦ Schulz, Frank ♦ Wagner, Dorothea ♦ Prasinos, Grigorios ♦ Zaroliagis, Christos Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Divide-and-conquer ♦ Planar graph ♦ Separator Abstract We consider classical linear-time planar separator algorithms, determining for a given planar graph a small subset of its nodes whose removal divides the graph into two components of similar size. These algorithms are based on planar separator theorems, which guarantee separators of size $\textit{O}(&sqrt;\textit{n})$ and remaining components of size at most $2\textit{n}/3$ (where $\textit{n}$ denotes the number of nodes in the graph). In this article, we present a comprehensive experimental study of the classical algorithms applied to a large variety of graphs, where our main goal is to find separators that do not only satisfy upper bounds, but also possess other desirable characteristics with respect to separator size and component balance. We achieve this by investigating a number of specific alternatives for the concrete implementation and fine-tuning of certain parts of the classical algorithms. It is also shown that the choice of several parameters influences the separation quality considerably. Moreover, we propose as planar separators the usage of fundamental cycles, whose size is at most twice the diameter of the graph: For graphs of small diameter, the guaranteed bound is better than the $\textit{O}(&sqrt;\textit{n})$ bounds, and it turns out that this simple strategy almost always outperforms the other algorithms, even for graphs with large diameter. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2010-01-05 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 14 Page Count 27 Starting Page 1.5 Ending Page 1.31

#### Open content in new tab

Source: ACM Digital Library