DIOT, Emilie; GAVOILLE, Cyril

doi:10.1016/j.endm.2009.07.091

Métadonnées

Licence d’utilisation du document

DIOT, Emilie
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

Langue

Communication dans un congrès

Ce document a été publié dans

EuroComb 2009, EuroComb 2009, EuroComb 2009, Bordeaux, France, 2009-09-07, Bordeaux. 2009-09, vol. 34C, p. 549-552

Résumé en anglais

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.< Réduire

Mots clés en anglais

treewidth

planar graphs

path-separable

Métadonnées

Partager cette publication !

Licence d’utilisation du document

On the Path Separability of Planar Graphs

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche