Embedded-width: A variant of treewidth for plane graphs

Hung Le, Glencora Borradaile, Jeff Erickson, Hung Le 0001, Robbie WeberarXiv 2017 · arXiv

Introduction

Treewidth is a fundamental parameter in graph theory, serving as a measure of how closely a graph resembles a tree. For graphs with low treewidth, many NP-hard problems become solvable in polynomial time via dynamic programming. However, computing the treewidth of a general graph is NP-hard, and its complexity remains an open question for the specific class of planar graphs—graphs that can be drawn in a 2D plane without edges crossing.

This paper introduces embedded-width (em-width), a variant of treewidth specifically tailored for plane graphs (graphs already provided with a fixed 2D embedding). By requiring tree decompositions to respect the graph's faces, the authors provide a new framework for designing planar algorithms and present a linear-time algorithm for calculating this width that is more efficient than previous general-purpose methods.

Defining Embedded-Width

Standard treewidth is "embedding-agnostic," meaning it only considers the connectivity of the graph. In contrast, em-width forces the tree decomposition to "pay attention" to the faces of the graph. The authors define an embedded tree decomposition as a standard tree decomposition with one additional constraint: for every bounded face in the graph, there must be at least one "bag" (a node in the decomposition tree) that contains every vertex on that face's boundary.

To bridge the gap between abstract structure and geometric representation, the authors introduce facial completion. This is a process where a clique (a fully connected sub-graph) is added to every face of the graph. A key theoretical result of the paper is that the treewidth of this completed graph is exactly the em-width of the original plane graph.

Algorithmic Approach

A primary contribution of this work is a fixed-parameter tractable (FPT) algorithm that decides if a graph has em-width $k$ in linear time, $O(n)$. The algorithm relies on recursive contraction, where the graph is repeatedly shrunk by finding and contracting "matchings" (pairs of connected vertices).

Handling r-families

The main obstacle to finding large matchings in planar graphs is the presence of r-families—groups of degree-2 vertices that share the same neighbors. The authors identify "nicely embedded r-families" as a geometric constraint that allows them to guarantee the existence of a large matching. By developing specific reduction rules for these families, the algorithm reduces the graph size by a constant factor (specifically 1/37) in each step. This represents a significant simplification and improvement over Bodlaender’s classic general-purpose algorithm, which utilized much smaller reduction factors.

Key Results and Theoretical Bounds

The paper establishes several important relationships between em-width, standard treewidth ($tw$), and the maximum face length ($\ell$):

  • General Bound: For a plane graph $G$, the em-width is at most $(tw(G) + 2) \cdot \ell - 1$.
  • Outerplanar Bound: For $k$-outerplanar graphs (graphs drawn in $k$ layers), the bound is tighter: $emw(G) \le 3k\ell - 1$.
  • Triangulation: For triangulated planar graphs (where every face is a triangle), em-width and treewidth are essentially equivalent, showing that em-width is a natural extension of the treewidth concept into the planar domain.

Limitations and Future Directions

Despite its algorithmic advantages, em-width is inherently dependent on the specific embedding provided. The same planar graph could have different em-widths depending on how it is drawn, and this paper does not provide a method for finding the optimal embedding to minimize width. Additionally, while the algorithm is linear in terms of the number of vertices ($n$), it remains exponential in terms of the width parameter $k$.

Ultimately, the authors suggest that em-width could serve as a vital stepping stone toward resolving the long-standing question of whether calculating the standard treewidth of planar graphs is NP-hard.

Summary updated

Abstract

We define a special case of tree decompositions for planar graphs that respect a given embedding of the graph. We study the analogous width of the resulting decomposition we call the embedded-width of a plane graph. We show both upper bounds and lower bounds for the embedded-width of a graph in terms of its treewidth and describe a fixed parameter tractable algorithm to calculate the embedded-width of a plane graph. To do so, we give novel bounds on the size of matchings in planar graphs.
BibTeX
@misc{le2017embedded,
  author = {Hung Le and Glencora Borradaile and Jeff Erickson and Hung Le and Robbie Weber},
  title = {{Embedded-width: A variant of treewidth for plane graphs}},
  year = {2017},
  eprint = {1703.07532},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1703.07532},
}
Figure