## 3 Algorithm for a Restricted Case
\(M[s,t]\) stores the size of MCS between \(G_{1}(u,C)\) and \(G_{2}(v,D)\) up to \(u_{s}\) and \(v_{t}\), respectively. \(flag\) is introduced to ensure the connectedness of a common subgraph. For example, \(flag=0\) if \(G_{1}(u)\) is a triangle, but \(G_{2}(v)\) is a rectangle. If \(C\) (and also \(D\)) is an edge, \(flag=0\), but the procedure returns \(M[1,1]\). **for all \((s,t)\in\{1,\ldots,h\}\times\{1,\ldots,k\}\) do**  
\(M[s,t]\gets 1+MCS_{c}(G_{1}(u_{s}),G_{2}(v_{t}))\);  
\(flag\gets 0\);  
**for \(s=2\) to \(h\) do**  
**for \(t=2\) to \(k\) do**  
\(M[s,t]\gets M[s,t]+\max_{s^{\prime}<s,t^{\prime}<t}\{M[s^{\prime},t^{ \prime}]+MCS_{p}(G_{1}(u_{s^{\prime}},u_{s}),G_{2}(u_{t^{\prime}},u_{t}))\}\);  
**if \(M[s,t]>-\infty\) then \(flag\gets 1\)**;  
**if \(C\)** is a block and \(flag=0\) then return \(0\) else return \(\max_{s,t}M[s,t]\). **Computation of \(MCS_{p}(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\)**  
Let \((u_{1},u_{2},\ldots,u_{h})\) be the sequence of vertices in \(G_{1}(u,u^{\prime})\), such that there exists an edge \(\{u_{i},u\}\) or \(\{u_{i},u^{\prime}\}\) for each \(u_{i}\), where \(u_{1},u_{2},\ldots,u_{h}\) are arranged in clockwise order. \((v_{1},v_{2},\ldots,v_{k})\) is defined for \(G_{2}(v,v^{\prime})\) in the same way. For a pair, \((u_{i},v_{j})\), \(l(u_{i},v_{j})=1\) if \(\{u_{i},u\}\in E_{1}\) and \(\{v_{j},v\}\in E_{2}\) hold,  
\[X = \{C_{1},\ldots,C_{h_{1}},e_{1},\ldots,e_{h_{2}}\}\]2 Computation of \(MCS_{b}(G_{1}(u,C),G_{2}(v,D))\). otherwise, \(l(u_{i},v_{j})=0\). Similarly, for a pair, \((u_{i},v_{j})\), \(r(u_{i},v_{j})=1\) if \(\{u_{i},u^{\prime}\}\in E_{1}\) and \(\{v_{j},v^{\prime}\}\in E_{2}\) hold, otherwise, \(r(u_{i},v_{j})=0\). We compute \(MCS_{p}(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\) by the following procedure, where it does not examine alignments with \(j_{g}<j_{g-1}<\cdots<j_{1}\):  
Procedure \(SimpleOuterMCS_{p}(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\)  
**if**\(\{u,u^{\prime}\}\in E_{1}\) and \(\{v,v^{\prime}\}\in E_{2}\)**then**\(s_{\max}\gets 1\)**else**\(s_{\max}\leftarrow-\infty\);  
**for all** alignments \(((u_{i_{1}},u_{i_{2}},\ldots,u_{i_{g}}),(v_{j_{1}},v_{j_{2}},\ldots,v_{j_{g}}))\)**do**  
**if**\(l(u_{i_{t}},v_{j_{t}})=0\) and \(r(u_{i_{t}},v_{j_{t}})=0\) hold for some \(t\)**then continue**;  
**if**\(l(u_{i_{1}},v_{j_{1}})=0\) or \(r(u_{i_{g}},v_{j_{g}})=0\) holds **then continue**;  
**if**\(\{u,u^{\prime}\}\in E_{1}\) and \(\{v,v^{\prime}\}\in E_{2}\)**then**\(s\gets 1\)**else**\(s\gets 0\);  
**for**\(t=1\)**to**\(g\)**do**\(s\gets s+l(u_{i_{t}},v_{j_{t}})+r(u_{i_{t}},v_{j_{t}})+MCS_{c}(G_{1}(u_{i_{t}}),G_{2}(v_{j_{t}}))\);  
**for**\(t=2\)**to**\(g\)**do**\(s\gets s+MCS_{p}(G_{1}(u_{i_{t-1}},u_{i_{t}}),G_{2}(v_{j_{t-1}},v_{j_{t}}))\);  
\(s_{\max}\leftarrow\max(s,s_{\max})\);  
**return**\(s_{\max}\). This procedure returns \(-\infty\) if there is no connected common subgraph between \(G_{1}(u,u^{\prime})\) and \(G_{2}(v,v^{\prime})\) that contains \((w,w^{\prime})\) corresponding to both \((u,u^{\prime})\) and \((v,v^{\prime})\). It should be noted that the first line in the body of the main loop puts the constraint that all corresponding pairs, \((u_{i_{t}},v_{j_{t}})\), in an alignment must be connected to either \((u,v)\) or \((u^{\prime},v^{\prime})\), and the second line puts the constraint that \((u_{i_{1}},v_{j_{1}})\) must be connected to \((u,v)\) and \((u_{i_{g}},v_{j_{g}})\) must be connected to \((u^{\prime},v^{\prime})\). As an example, consider an alignment, \(((u_{1},u_{2},u_{3},u_{4}),(v_{1},v_{2},v_{3},v_{5}))\), in \[X = \{C_{1},\ldots,C_{h_{1}},e_{1},\ldots,e_{h_{2}}\}\]3 Then, the score is given by \(4+MCS_{p}(G_{1}(u_{1},u_{2}),G_{2}(v_{1},v_{2}))+MCS_{p}(G_{1}(u_{2},u_{3}),\)\(G_{2}(v_{2},v_{3}))+MCS_{b}(G_{1}(u_{3},C_{3}),G_{2}(v_{3},D_{4}))+MCS_{p}(G_{1}(u_{3}, u_{4}),G_{2}(v_{3}.v_{5}))\), where \(MCS_{b}(G_{1}(u_{3},C_{3}),G_{2}(v_{3},D_{4}))\) is given via the computation of \(MCS_{c}(G_{1}(u_{3}),G_{2}(v_{3}))\).