KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
DOI: 10.5445/IR/1000003518

Engineering planar separator algorithms

Holzer, Martin; Prasinos, Grigorios; Schulz, Frank; Wagner, Dorothea; Zaroliagis, Christos


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 asymptotically in the
square root of the number of nodes 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 bounds of the classical
algorithms, and it turns out that this simple strategy almost
always outperforms the other algorithms, even for graphs with
large diameter.

Zugehörige Institution(en) am KIT Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Publikationstyp Forschungsbericht
Jahr 2005
Sprache Englisch
Identifikator ISSN: 1432-7864
URN: urn:nbn:de:swb:90-35182
KITopen-ID: 1000003518
Verlag Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2005,20
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page