Diameter of Minimal Separators in Graphs

Description

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.

Abstract (French)

Nous \'etablissons des relations g\'en\'erales entre les propri\'et\'es topologiques des graphes et leurs propri\'et\'es m\'etriques.Dans ce but, nous bornons sup\'erieurement le diam\`etre des \emph{s\'eparateurs minimaux} dans un graphe par une fonction de leur taille.Plus pr\'ecis\'ement, nous prouvons que, dans n'importe quel graphe $G$, le diam\`etre de tout s\'eparateur minimal $S$ dans $G$ est au plus $\lfloor \frac{\ell(G)} {2}\rfloor \cdot (|S|-1)$ avec $\ell(G)$ la plus grande taille d'un cycle isom\'etrique dans $G$.Nous am\'eliorons cette borne dans le cas des graphes pour lesquels il existe un \emph{ordre d'\'elimination isom\'etrique}: nous prouvons que tout s\'eparareur minimal $S$ dans un tel graphe a pour diam\`etre au plus $2 (|S|-1)$. Nos preuves sont principalement bas\'ees sur le fait que les s\'eparateurs minimaux dans un graphe $G$ sont connexes dans l'une de ses puissances.Une cons\'equence facile de nos r\'esultats est que pour tout graphe $G$, la \emph{treelength} $tl(G)$ est au plus $\lfloor \frac{\ell(G)} {2}\rfloor$ fois sa \emph{treewidth} $tw(G)$.En compl\'ement de cette relation, nous prouvons que, pour tout graphe $G$ qui exclut un \emph{apex graph} $H$ comme mineur, $tw(G) \leq c_H \cdot tl(G)$ avec $c_H$ une constante qui ne d\'epend que de $H$.Nous am\'eliorons cette constante dans le cas o\`u $G$ est de genre born\'e.En cons\'equence de quoi, nous obtenons un algorithme tr\`es simple avec facteur d'approximation $O(\ell(G))$ pour calculer la treewidth des graphes qui excluent un apex graph comme mineur en temps $O(n m)$.

Additional details