Path Separability of Graphs

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

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

In this paper we investigate the structural properties of $k$-path separable graphs, that are the graphs that can be separated by a set of $k$ shortest paths. We identify several graph families having such path separability, and we show that this property is closed under minor taking. In particular we establish a list of forbidden minors for $1$-path separable graphs.

Mots clés: shortest path; separator; graph minor theory; graph algorithms

Domaines: Algorithme et structure de données [cs.DS]; Mathématique discrète [cs.DM]

Emilie Diot, Cyril Gavoille. Path Separability of Graphs. 2010. ⟨hal-00507833v3⟩