## 4 Algorithm for Outerplanar Graphs of Bounded Degree
### Analysis  
As mentioned before, each blade is specified by base and tip vertices in \(G_{1}\) or \(G_{2}\) and an orientation. Each half block is also specified by two vertices in a block in \(G_{1}\) or \(G_{2}\). We show that this property is maintained throughout the execution of the algorithm and bound to the number of half blocks and blades, as below. **Lemma 1**: _The number of different half blocks and blades appearing in \(OuterMCS(G_{1},G_{2})\) is \(O(n^{2})\)._  
_Proof._ We prove it by mathematical induction on the number of steps in the execution of the algorithm. At the beginning of the algorithm, this property is trivially maintained, because we only have \(G_{1}\) and \(G_{2}\). A new half block (along with its descendants) or a new blade is created only when graphs are modified according to a configuration or alignment. In the alignment case, it is straightforward to see that new half blocks are half blocks of the current block or current half block. It can also be seen that whenever a blade is newly created, it is a half block (along with descendants) of the current block or current half block. The crucial cases lie when an existing blade is modified according to a configuration. Let \(u\) and \(\{u,w\}\) be the base vertex and a backbone edge in a blade \(BD\), respectively. Let \(C_{0}\) be the block in \(G_{1}\) (resp. \(G_{2}\)) from which \(BD\) was created. Then, we need to consider the following three cases (Figure 10) ( new blades may also be created by a tip edge in a half block specified by a pair of selected vertices):  
* \(w\) is not selected. The base vertex of a new blade is the selected vertex nearest to \(w\) in the first block (_i.e._, block containing \(u\)) of \(BD\). Since the original blade body was a half block of a block \(C_{0}\), the resulting blade body is also a half block of \(C_{0}\). * \(w\) is selected, and there is no tip edge between \(w\) and its nearest selected vertex. The resulting blade body begins from \(w\) (in the next step), which is a half block of \(C_{0}\). * \(w\) is selected, and there is a tip edge between \(w\) and its nearest selected vertex. The resulting blade body begins from \(w\), which is a half block of \(C_{0}\). Furthermore, two (or less) new blade bodies are created, both of which are half blocks of \(C_{0}\). Therefore, we can see that every half block or blade appearing in the algorithm is specified by two vertices in a block of \(G_{1}\) or \(G_{2}\), from which the lemma follows. \(\Box\)  
Finally, we obtain the following theorem. **Theorem 2**: _A maximum common connected edge subgraph of two outerplanar graphs of bounded degree can be computed in polynomial-time._  
_Proof._ It is straightforward to check the correctness of the algorithm, because it implicitly examines all possible common subgraphs via alignment, decomposition by configurations and bipartite matching, where Fact 1 enables us to use alignment and dynamic programming. Therefore, we focus on the time complexity. Since the number of half blocks and blades is \(O(n^{2})\) and the maximum degree is bounded, the number of different \(G_{1}(u)\)'s and \(G_{1}(u,u^{\prime})\)'s (resp. \(G_{2}(v)\)'s and \(G_{2}(v,v^{\prime})\)'s) appearing in the algorithm, some of which can be obtained from subgraphs of \(G_{1}\) (resp. \(G_{2}\)), is \(O(n^{3})\), where an additional \(O(n)\) factor comes from the fact that \(O(n)\) new blocks and bridges may be created per blade. Therefore, we can transform the recursive algorithm into a dynamic programming algorithm using \(O(n^{3})\times O(n^{3})=O(n^{6})\) size tables. For each subgraph appearing in \(OuterMCS(G_{1}(u),G_{2}(v))\) or \(OuterMCS(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\) as an argument, the number of configurations is \(O(n^{2D-3})\), because there exists at most \(2D-2\) neighboring vertices (excluding those nearer to the root) of \(u\) and \(u^{\prime}\) (resp. \(v\) and \(v^{\prime}\)) for a constant, \(D\), (\(D>2\)) and a tip edge lies between a path connecting two neighboring vertices.