## 3 Algorithm for a Restricted Case  
In this section, we consider the following restricted variant of OUTER-MCS, which is called SIMPLE-OUTER-MCS, and present a polynomial-time algorithm for it: (i) any two vertices in different biconnected components in a maximum common subgraph, \(G_{c}\), must not be mapped to vertices in the same biconnected component in \(G_{1}\) (resp. \(G_{2}\)); (ii) each bridge in \(G_{c}\) must be mapped to a bridge in \(G_{1}\) (resp. \(G_{2}\)); (iii) the maximum degree need not be bounded. It is to be noted from the definition of a common subgraph (regardless of the above restrictions) that no two vertices in different biconnected components in \(G_{1}\) (resp. \(G_{2}\)) are mapped to vertices in the same biconnected component in any common subgraph, and no bridge in \(G_{1}\) (resp. \(G_{2}\)) is mapped to an  
Figure 1: Example of an outerplanar graph. edge in a block in any common subgraph (otherwise there would exist a cycle containing the edge in a common subgraph, which would mean that the edge in \(G_{1}\) (resp., \(G_{2}\)) is not a bridge). SIMPLE-OUTER-MCS is intrinsically the same as the one studied by [PERSON] _et al_. [11]. Although our algorithm is more complex and less efficient than their algorithm, we present it here, because the algorithm for a general (but bounded degree) case is rather involved and is based on our algorithm for SIMPLE-OUTER-MCS. Procedure  
\(SimpleOuterMCS(G_{1},G_{2})\)  
\(s_{\max}\gets 0\);  
**for all** pairs of vertices \((u,v)\in V_{1}\times V_{2}\)**do**  
Let \((u,v)\) be the root pair \((r_{1},r_{2})\) of \((G_{1},G_{2})\);  
\(s_{\max}\leftarrow\max(s_{\max},MCS_{c}(G_{1}(r_{1}),G_{2}(r_{2})))\);  
**return**\(s_{\max}\). The algorithm consists of a recursive computation of the following three scores:  
\(MCS_{c}(G_{1}(u),G_{2}(v))\)**:**: the size of an MCS \(G_{c}\) between \(G_{1}(u)\) and \(G_{2}(v)\), where \((u,v)\) is a pair of the roots or a pair of cut vertices, and \(G_{c}\) must contain a vertex corresponding to both \(u\) and \(v\). \(MCS_{b}(G_{1}(u,C),G_{2}(v,D))\)**:**: the size of an MCS \(G_{c}\) between \(G_{1}(u,C)\) and \(G_{2}(v,D)\), where \((C,D)\) is either a pair of blocks or a pair of bridges, \(u\) (resp. \(v\)) is the cut vertex belonging to both \(C\) (resp. \(D\)) and its parent, \(G_{c}\) must contain a vertex corresponding to both \(u\) and \(v\) and \(G_{c}\) must contain a biconnected component (which can be empty) corresponding to a subgraph of \(C\) and a subgraph \(D\). \(MCS_{p}(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\)**:**: the size of an MCS \(G_{c}\) between \(G_{1}(u,u^{\prime})\) and \(G_{2}(v,v^{\prime})\), where \((u,u^{\prime})\) (resp. \((v,v^{\prime})\)) is a cut pair, and \(G_{c}\) must contain a cut pair \((w,w^{\prime})\) corresponding to both \((u,u^{\prime})\) and \((v,v^{\prime})\). If there does not exist such \(G_{c}\) (which must be connected), its score is \(-\infty\). In the following, we describe how to compute these scores. **Computation of \(MCS_{c}(G_{1}(u),G_{2}(v))\)**  
As in the dynamic programming algorithm for MCS for trees or almost trees [9], we construct a bipartite graph and compute a maximum weight matching. Let \(C_{1},\ldots,C_{h_{1}},e_{1},\ldots,e_{h_{2}}\) and \(D_{1},\ldots,D_{k_{1}},f_{1},\ldots,f_{k_{2}}\) be children of \(u\) and \(v\) respectively, where \(C_{i}\)'s and \(D_{j}\)'s are blocks and \(e_{i}\)'s and \(f_{j}\)'s are bridges (see Figure 2). We construct an edge-weighted bipartite graph \(BG(X,Y;E)\) by  
\[X = \{C_{1},\ldots,C_{h_{1}},e_{1},\ldots,e_{h_{2}}\}\] \[Y = \{D_{1},\ldots,D_{k_{1}},f_{1},\ldots,f_{k_{2}}\}\] \[E = \{(x,y)\mid x\in X,y\in Y\}\] \[w(C_{i},f_{j}) = 0\]\[w(C_{i},D_{j}) = MCS_{b}(G_{1}(u,C_{i}),G_{2}(v,D_{j}))\] \[w(e_{i},D_{j}) = 0\] \[w(e_{i},f_{j}) = MCS_{b}(G_{1}(u,e_{i}),G_{2}(v,f_{j}))\]  
Then, we let \(MCS_{c}(G_{1}(u),G_{2}(v))\) be the weight of the maximum weight bipartite matching of \(BG(X,Y;E)\).