## 4 Algorithm for Outerplanar Graphs of Bounded Degree
### Description of Algorithm  
In this subsection, we describe the algorithm as a recursive procedure, which can be transformed into a dynamic programming one, as stated in Section 3. The main procedure, \(OuterMCS(G_{1},G_{2})\) is the same as that mentioned in Section 3, and we recursively compute three kinds of scores: \(MCS_{c}(G_{1}(u),G_{2}(v))\), \(MCS_{b}(G_{1}(u,C),\)\(G_{2}(v,D))\) and \(MCS_{p}(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\), where cut vertices, cut pairs, blocks and bridges do not necessarily mean those in the original graphs, but may mean those in subgraphs generated by the algorithm. **Computation of \(MCS_{c}(G_{1}(u),G_{2}(v))\)**  
Let \(C_{1},\ldots,C_{h_{1}}\) and \(e_{1},\ldots,e_{h_{2}}\) be children of \(u\), where \(C_{i}\)'s and \(e_{j}\)'s are blocks and bridges, respectively. Let \(u_{i_{1}},\ldots,u_{i_{h}}\) be the neighboring vertices of \(u\) that are contained in the children of \(u\). We define a _configuration_ as a tuple of the following (see Figure 8). \(s(u_{i_{j}})\in\{0,1\}\) for \(j=1,\ldots,k\): \(s(u_{i_{j}})=1\) means that \(u_{i_{j}}\) is selected as a neighbor of \(u\) in a common subgraph, otherwise \(s(u_{i_{j}})=0\). \(u_{i_{j}}\) is called a _selected vertex_ if \(s(u_{i_{j}})=1\). \(tip(u_{i_{j}},u_{i_{k}})\): \(e=tip(u_{i_{j}},u_{i_{k}})\) is an edge in \(B(u_{i_{j}},u_{i_{k}})\), where \(B\) is the block containing \(u_{i_{j}}\), \(u_{i_{k}}\) and \(u\). This edge is defined only for a consecutive selected vertex pair, \(u_{i_{j}}\) and \(u_{i_{k}}\), in the same block (_i.e._, \(B(u_{i_{j}},u_{i_{k}})\) does not contain any other selected vertex). \(e\) is used as a tip edge, where \(e\) can be empty, which means that we do not cut any edge in \(B(u_{i_{j}},u_{i_{k}})\). It is to be noted that, at most, one edge in \(B(u_{i_{j}},u_{i_{k}})\) can be a tip edge, and thus, each \(B(u_{i_{j}},u_{i_{k}})\) is divided into, at most, two blade bodies; further decomposition will be done in later steps. We also consider \(\overline{e}\) and \(\hat{e}\) for \(e=tip(u_{i_{j}},u_{i_{k}})\) whenever available. Each configuration defines a subgraph of \(G_{1}(u)\) as follows:  
* \(e_{i}=\{u_{i_{j}},u\}\) (\(i\in\{1,\ldots,h_{2}\}\)) remains if \(s(u_{i_{j}})=1\). Otherwise, \(e_{i}\) is removed along with its descendants. * If no vertex in \(C_{i}\) is selected, it is removed along with its descendants. Otherwise, \(C_{i}\) is divided into blocks, blade bodies (according to \(s(\ldots)\)'s and \(tip(\ldots)\)'s) and bridges, where edges, \(\{u_{i_{j}},u\}\) with \(s(u_{i_{j}})=0\), are removed. Let \(C^{\prime}_{1},\ldots,C^{\prime}_{p_{1}}\) and \(e^{\prime}_{1},\ldots,e^{\prime}_{p_{2}}\) be the resulting blocks and bridges containing \(u\), which are new 'children' of \(u\), for a configuration, \(F_{1}\). Configurations are defined for \(G_{2}(v)\) in an analogous way. Let \(D^{\prime}_{1},\ldots,D^{\prime}_{q_{1}}\) and \(f^{\prime}_{1},\ldots,f^{\prime}_{q_{2}}\) be the resulting new children of \(v\) for a configuration \(F_{2}\) of \(G_{2}\). As stated in Section 3, we construct a bipartite graph \(BG_{F_{1},F_{2}}\) by  
\[w(C^{\prime}_{i},f^{\prime}_{j}) = 0\] \[w(C^{\prime}_{i},D^{\prime}_{j}) = MCS_{b}(G_{1}(u,C^{\prime}_{i}),G_{2}(v,D^{\prime}_{j}))\] \[w(e^{\prime}_{i},D^{\prime}_{j}) = 0\] \[w(e^{\prime}_{i},f^{\prime}_{j}) = MCS_{b}(G_{1}(u,e^{\prime}_{i}),G_{2}(v,f^{\prime}_{j}))\]  
and we compute the weight of the maximum weight matching for each configuration pair \((F_{1},F_{2})\) ( although a bridge cannot be mapped on a block here, a bridge can be mapped to an edge in a block ofan input graph by converting the block into smaller blocks and bridges using tip edge(s)).