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 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