On the Path Separability of Planar Graphs

Emilie Diot (1, 2) , Cyril Gavoille (1, 2)

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms

It is known that every weighted planar graph with n vertices contains three shortest paths whose removal halves the graph into connected components of at most n/2 vertices. It is open whether this property remains true with the use of two shortest paths only. We show that two shortest paths are enough for a large family of planar graphs, called face-separable, composed of graphs for which every induced subgraph can be halved by removing the border of a face in some suitable embedding of the subgraph. We also show that this non-trivial family of graphs includes unbounded treewidth graphs.

Mots clés: treewidth; planar graphs; path-separable

Domaines: Algorithme et structure de données [cs.DS]

Emilie Diot, Cyril Gavoille. On the Path Separability of Planar Graphs. EuroComb 2009, Bordeaux, France, Sep 2009, Bordeaux, France. pp.549-552, ⟨10.1016/j.endm.2009.07.091⟩. ⟨hal-00408228⟩