On the diameter of minimal separators in a graph

Abstract:

The so-called topological and metric tree-likeness invariants are two distinct approaches to measure “how close” a graph is from a tree. They are related with tree-decompositions of the graph. In this work, we focus on the relations between topological and metric graph parameters, and especially between treewidth and treelength. Our main contribution is a general upper-bound on the diameter of minimal separators in a graph that depends on the properties of its cycle basis. This allows us to show the treelength is upper-bounded by an O(l(G).tw(G)), with tw(G) the treewidth and l(G) the length of a longest isometric cycle in the graph. Then, extending a previous result from Diouf and Gavoille for planar graphs, we prove that tw(G) = O(tl(G)) for apex-minor-free graphs. Altogether, our results provide a very simple constant-factor approximation algorithm for treewidth in graphs with bounded-genus and isometric cycles of bounded length.

Posted on Nov 24, 2014 in Discrete Mathematics, Seminars