On the Path Separability of Planar Graphs
DIOT, Emilie
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
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]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
DIOT, Emilie
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
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]
< Reduce
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Language
en
Communication dans un congrès
This item was published in
EuroComb 2009, EuroComb 2009, EuroComb 2009, Bordeaux, France, 2009-09-07, Bordeaux. 2009-09, vol. 34C, p. 549-552
English Abstract
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 ...Read more >
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.Read less <
English Keywords
treewidth
planar graphs
path-separable
Origin
Hal imported