Skip to Main content Skip to Navigation
Conference papers

Treelength of Series-parallel graphs

Abstract : Thelengthof atree-decompositionof a graph is the maximum distance between twovertices of a same bag of the decomposition. Thetreelengthof a graph is the minimum lengthamong its tree-decomposition. Treelength of graphs has been studied for its algorithmicapplications in classical metric problems such as Traveling Salesman Problem or metricdimension of graphs and also, in compact routing in the context of distributed computing.Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs oftreelength one are precisely the chordal graphs), and it is known that the treelength of agraph cannot be approximated up to a factor less than32(the best known approximationalgorithm for treelength has an approximation ratio of 3). However, nothing is known onthe computational complexity of treelength in planar graphs, except that the treelength ofany outerplanar graph is equal to the third of the maximum size of its isometric cycles.This work initiates the study of treelength in planar graphs by considering its next naturalsubclass, namely the one of series-parallel graphs.We first fully describe the treelength of melon graphs (set of pairwise internally disjointpaths linking two vertices), showing that, even in such a restricted graph class, the expressionof the treelength is not trivial. Then, we show that treelength can be approximated up toa factor32in series-parallel graphs. Our main result is a polynomial-time algorithm fordeciding whether a series-parallel graph has treelength at most 2. Our latter result relies ona characterization of series-parallel graphs with treelength 2 in terms of an infinite family offorbidden isometric subgraphs.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03175837
Contributor : Nicolas Nisse <>
Submitted on : Sunday, March 21, 2021 - 3:08:19 PM
Last modification on : Wednesday, March 31, 2021 - 3:35:49 AM

File

Lagos_2021(9).pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03175837, version 1

Citation

Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle. Treelength of Series-parallel graphs. XI Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), 2021, São Paulo, Brazil. ⟨hal-03175837⟩

Share

Metrics

Record views

14

Files downloads

269