## 2 Preliminaries  
A graph is called _outerplanar_ if it can be drawn on a plane such that all vertices lie on the outer face (_i.e_., the unbounded exterior region) without crossing of edges. Although there exist many embeddings (_i.e_., drawings on a plane) of an outerplanar graph, it is known that one embedding can be computed in linear time. Therefore, in this paper, we assume that each graph is given with its planar embedding. A path is called _simple_ if it does not pass the same vertex multiple times. In this paper, a path always means a simple path that is not a cycle. A _cut vertex_ of a connected graph is a vertex whose removal disconnects the graph. A graph is _biconnected_ if it is connected and does not have a cut vertex. A maximal biconnected subgraph is called a _biconnected component_. A biconnected component is called a _block_ if it consists of at least three vertices; otherwise, it is an edge and called a _bridge_. An edge in a block is called an _outer_ edge if it lies on the boundary of the outer face; otherwise, it is called an _inner_ edge. It is well-known that any block of an outerplanar graph has a unique Hamiltonian cycle, which consists of outer edges only [20]. For the details of the terminology used in graphs and outerplanar graphs, refer to an appropriate textbook on graph theory (e.g., [21]). If we fix an arbitrary vertex of a graph \(G\) as the root \(r\), we can define the parent-child relationship on biconnected components. For two vertices, \(u\) and \(v\), \(u\) is called _further_ than \(v\) if every simple path from \(u\) to \(r\) contains \(v\). A biconnected component, \(C\), is called a _parent_ of a biconnected component \(C^{\prime}\) if \(C\) and \(C^{\prime}\) share a vertex \(v\), where \(v\) is uniquely determined, and every path from any vertex in \(C^{\prime}\) to the root contains \(v\). In such a case, \(C^{\prime}\) is called a _child_ of \(C\). A cut vertex \(v\) is also called a _parent_ of \(C\) if \(v\) is contained in both \(C\) and its parent component ( both of a cut vertex and a biconnected component can be parents of the same component). Furthermore, the root, \(r\), is a parent of \(C\) if \(r\) is contained in \(C\). For each cut vertex \(v\), \(G(v)\) denotes the subgraph of \(G\) induced by \(v\) and the vertices further than \(v\). For a pair of a cut vertex \(v\) and a biconnected component, \(C\), containing \(v\), \(G(v,C)\) denotes the subgraph of \(G\) induced by vertices in \(C\) and its descendant components. For a biconnected component, \(B\), with its parent cut vertex, \(w\), a pair of vertices, \(v\) and \(v^{\prime}\), in \(B\) is called a _cut pair_ if \(v\
eq v^{\prime}\), \(v\
eq w\) and \(v^{\prime}\
eq w\) hold. For a cut pair \((v,v^{\prime})\) in \(B\), \(VB(v,v^{\prime})\) denotes the set of the vertices lying on the one of the two paths connecting \(v\) and \(v^{\prime}\) in the Hamiltonian cycle that does not contain the parent cut vertex, except its endpoints. \(B(v,v^{\prime})\) is the subgraph of \(B\) induced by \(VB(v,v^{\prime})\) and is called a _half block_. It is to be noted that \(B(v,v^{\prime})\) contains both \(v\) and \(v^{\prime}\). Then, \(G(v,v^{\prime})\) denotes the subgraph of \(G\) induced by \(VB(v,v^{\prime})\) and the vertices in the biconnected components, each of which is a descendant of some vertex in \(VB(v,v^{\prime})-\{v,v^{\prime}\}\), and \(\overline{G}(v,v^{\prime})\) denotes the subgraph of \(G\) induced by the vertices in \(G(v,v^{\prime})\) and descendant components of \(v\) and \(v^{\prime}\), where descendants are defined via the parent-child relationship. **Example** Figure 1 shows an example of an outerplanar graph \(G(V,E)\). Blocks and bridges are shown by gray regions and bold lines, respectively. \(B_{1}\), \(B_{3}\) and \(e_{2}\) are the children of the root \(r\). \(B_{4}\), \(B_{6}\) and \(B_{7}\) are the children of \(B_{3}\), whereas \(B_{4}\) and \(B_{6}\) are the children of \(w\). Both \(w\) and \(B_{3}\) are the parents of \(B_{4}\) and \(B_{6}\).