research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleEngineering Planar Separator Algorithms
Bibtex cite IDRACTI-RU1-2005-54
Booktitle 13th Annual European Symposium on Algorithms
Series Lecture Notes in Computer Science
Year published 2005
Month October
Volume 3669/2005
Pages 628-639
Organization ESA 2005
DOI 10.1007/11561071_56
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 MediaObjects/InlineFigure1.png 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 MediaObjects/InlineFigure2.png bounds, and it turns out that this simple strategy almost always outperforms the other algorithms, even for graphs with large diameter.
Holzer, M.
Prasinos, Grigorios
Schulz, Frank
Wagner, Dorothea
Zaroliagis, Christos
fulltext.pdf (main file)
Publication ID397