DIOT, Emilie; GAVOILLE, Cyril

doi:10.1016/j.endm.2009.07.091

Metadatos

Licencia de uso del documento

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]

Idioma

Communication dans un congrès

Este ítem está publicado en

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

Resumen en inglés

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.< Leer menos

Palabras clave en inglés

treewidth

planar graphs

path-separable

Metadatos

Compartir este ítem

Licencia de uso del documento

On the Path Separability of Planar Graphs

Idioma

Este ítem está publicado en

Resumen en inglés

Palabras clave en inglés

URI

DOI

Orígen

Centros de investigación