Graph Composition and Some Forbidden Subgraph Problems

Let \(G\) be a graph with \(r \geq 0\) special vertices, \(b_1, \ldots, b_r\), called pins. \(G\) can be composed with another graph \(H\) by identifying each \(b_i\) with another vertex \(a_i\) of \(H\). The resulting graph is denoted \(H \circ G\). Let \(\Pi\) denote a decision problem on graphs. We consider the problem of constructing a “small” minor \(G^*\) of \(G\) that is “equivalent” to \(G\) with respect to the problem \(\Pi\). Specifically, \(G^*\) should satisfy the following:

(C1) \(G^b\) has the same pins as \(G\).

(C2) \(\Pi(H \circ G^b) = \Pi(H \circ G)\) for every \(H\) for which \(H \circ G\) is defined.

(C3) \(|V(G^b)| + |E(G^b)| \leq c \cdot p\), where \(p\) is the number of pins of \(G\), \\and \(c\) is a constant depending only on \(\Pi\).

(C4) \(G^b\) is a minor of \(G\).

We provide linear-time algorithms for constructing such graphs when \(\Pi\) stands for either series-parallelness or outer-planarity. These algorithms lead to linear-time algorithms that determine whether a hierarchical graph is series-parallel or outer-planar and to linear-space algorithms for generating a forbidden subgraph of a hierarchical graph, when one exists.