Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Diameter of Minimal Separators in Graphs

David Coudert 1 Guillaume Ducoffe 1 Nicolas Nisse 1 
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We establish general relationships between the topological properties of graphs and their metric properties. For this purpose, we upper-bound the diameter of the {\it minimal separators} in any graph by a function of their sizes. More precisely, we prove that, in any graph $G$, the diameter of any minimal separator $S$ in $G$ is at most $\lfloor\frac{\ell(G)} {2}\rfloor \cdot (|S|-1)$ where $\ell(G)$ is the maximum length of an isometric cycle in $G$. We refine this bound in the case of graphs admitting a {\it distance preserving ordering} for which we prove that any minimal separator $S$ has diameter at most $2 (|S|-1)$. Our proofs are mainly based on the property that the minimal separators in a graph $G$ are connected in some power of $G$.Our result easily implies that the {\it treelength} $tl(G)$ of any graph $G$ is at most $\lfloor \frac{\ell(G)} {2}\rfloor$ times its {\it treewidth} $tw(G)$. In addition, we prove that, for any graph $G$ that excludes an {\it apex graph} $H$ as a minor, $tw(G) \leq c_H \cdot tl(G)$ for some constant $c_H$ only depending on $H$. We refine this constant when $G$ has bounded genus. As a consequence, we obtain a very simple $O(\ell(G))$-approximation algorithm for computing the treewidth of $n$-node $m$-edge graphs that exclude an apex graph as a minor in $O(n m)$-time.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Friday, December 19, 2014 - 1:36:16 PM
Last modification on : Wednesday, October 26, 2022 - 8:15:07 AM
Long-term archiving on: : Saturday, April 15, 2017 - 8:38:23 AM


Files produced by the author(s)


  • HAL Id : hal-01088423, version 2



David Coudert, Guillaume Ducoffe, Nicolas Nisse. Diameter of Minimal Separators in Graphs. [Research Report] RR-8639, Inria Sophia Antipolis; I3S; INRIA. 2014, pp.16. ⟨hal-01088423v2⟩



Record views


Files downloads