Some Recent Progress and Applications in Graph Minor Theory

In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful theorem capturing the ``rough' structure of graphs excluding a fixed minor. This result was used to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation. Recently, a number of beautiful results that use this structural result have appeared. Some of these along with some other recent advances on graph minors are surveyed. Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, Grant number 16740044, by Sumitomo Foundation, by C & C Foundation and by Inoue Research Award for Young Scientists Supported in part by the Research Grant P1–0297 and by the CRC program On leave from: IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia     

On compact and efficient routing in certain graph classes

In this paper we refine the notion of tree-decomposition by introducing acyclic (R,D)-clustering, where clusters are subsets of vertices of a graph and R and D are the maximum radius and the maximum diameter of these subsets. We design a routing scheme for graphs admitting induced acyclic (R,D)-clustering where the induced radius and the induced diameter of each cluster are at most 2. We show that, by constructing a family of special spanning trees, one can achieve a routing scheme of deviation Δ?2R with labels of size bits per vertex and O(1) routing protocol for these graphs. We investigate also some special graph classes admitting induced acyclic (R,D)-clustering with induced radius and diameter less than or equal to 2, namely, chordal bipartite, homogeneously orderable, and interval graphs. We achieve the deviation Δ=1 for interval graphs and Δ=2 for chordal bipartite and homogeneously orderable graphs.     

New lower bounds for bin packing problems with conflicts

The bin packing problem with conflicts (BPC) consists of minimizing the number of bins used to pack a set of items, where some items cannot be packed together in the same bin due to compatibility restrictions. The concepts of dual-feasible functions (DFF) and data-dependent dual-feasible functions (DDFF) have been used in the literature to improve the resolution of several cutting and packing problems. In this paper, we propose a general framework for deriving new DDFF as well as a new concept of generalized data-dependent dual-feasible functions (GDDFF), a conflict generalization of DDFF. The GDDFF take into account the structure of the conflict graph using the techniques of graph triangulation and tree-decomposition. Then we show how these techniques can be used in order to improve the existing lower bounds.     

Linear connectivity forces large complete bipartite minors: An alternative approach

The recent paper ‘Linear connectivity forces large complete bipartite minors’ by Böhme, Kawarabayashi, Maharry and Mohar relies on an extension of Robertson and Seymour?s structure theorem for graphs with a forbidden minor. We describe a more direct approach which uses just the original structure theorem.     

Tree-decompositions with bags of small diameter

This paper deals with the length of a Robertson-Seymour's tree-decomposition. The tree-length of a graph is the largest distance between two vertices of a bag of a tree-decomposition, minimized over all tree-decompositions of the graph. The study of this invariant may be interesting in its own right because the class of bounded tree-length graphs includes (but is not reduced to) bounded chordality graphs (like interval graphs, permutation graphs, AT-free graphs, etc.). For instance, we show that the tree-length of any outerplanar graph is ⌈k/3⌉, where k is the chordality of the graph, and we compute the tree-length of meshes.More fundamentally we show that any algorithm computing a tree-decomposition approximating the tree-width (or the tree-length) of an n-vertex graph by a factor α or less does not give an α-approximation of the tree-length (resp. the tree-width) unless if α=Ω(n^1/5). We complete these results presenting several polynomial time constant approximate algorithms for the tree-length.The introduction of this parameter is motivated by the design of compact distance labeling, compact routing tables with near-optimal route length, and by the construction of sparse additive spanners.     

Vertex-minor reductions can simulate edge contractions

We prove that local complementation and vertex deletion, operations from which vertex-minors are defined, can simulate edge contractions. As an application, we prove that the rank-width of a graph is linearly bounded in term of its tree-width.