Separating an r-outerplanar graph into gluable pieces
René van Bevern, Iyad A. Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge · arXiv (Cornell University) · 2015
Let G be an r-outerplanar graph with n vertices. We provide a sequence of log(n)/(r+1)^(32r^2 +8r) separators in G, each containing a fixed number (at most 2r) of integer- labeled vertices and each separating the graph in a well-defined left and right side such that the following two conditions are fulfilled. (1) The separators are nested, meaning that the left side of every separator S is contained in all the left sides of separators followin S. (2) For each pair of separators, glueing the left side of the first and the right side of the second separator results in an r-outerplanar graph. Herein, gluing means to take the disjoint union and identify the vertices in the separators with the same labels. We apply the sequences as above to the problem of finding an r-outerplanar hypergraph support. That is, the problem is for a given hypergraph to find an r-outerplanar graph on the same vertex set such that each hyperedge induces a connected subgraph. We give an alternative proof that this problem is (strongly uniformly) fixed-parameter tractable with respect to r + m where m is the number of hyperedges in the hypergraph.