Alexander Grigoriev (Maastricht University)
The wall-by-wall distance
Abstract: We define a new metric on planar graphs, called the wall-by-wall distance, where two vertices are said to have a wall-by-wall distance of k if there exists a sequence of k edges such that every two consequent edges are adjacent and lie on the boundary of the same face. We consider the class of r-flat graphs, G^r, that contains a graph G if there exists a plane graph H such that G is a subgraph of H^r with respect to the new metric. Our results imply that the class G^r is computationally equivalent to the class of graphs with bounded crossing parameter. Moreover, we prove that the branchwidth of G^r is upper-bounded by a function of r and the branchwidth of G. Finally, making use of the wall-by-wall metric we provide an algorithmic scheme which handles problems for r-flat graphs related to a number of graph parameters, such as dominating set.