Access Restriction

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

   Open content in new tab
Source: ACM Digital Library