## 3 Algorithm for a Restricted Case
It is to be noted that \(w(C_{i},f_{j})=0\) (resp., \(w(e_{i},D_{j})=0\)) comes from the fact that \(f_{j}\) must be mapped to a bridge in \(G_{c}\), but a bridge in \(G_{c}\) must not be mapped to an edge in any block (e.g., \(C_{i}\)), because of the condition (ii) of SIMPLE-OUTER-MCS. **Computation of \(MCS_{b}(G_{1}(u,C),G_{2}(v,D))\)**  
Let \((u_{1},u_{2},\ldots,u_{h})\) be the sequence of vertices in \(G_{1}(u,C)\), such that there exists an edge, \(\{u_{i},u\}\), 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,D)\) in the same way. It is to be noted that \((C,D)\) is either a pair of blocks or a pair of bridges. A pair of subsequences \(((u_{i_{1}},u_{i_{2}},\ldots,u_{i_{g}}),(v_{j_{1}},v_{j_{2}},\ldots,v_{j_{g}}))\) is called an _alignment_ if \(i_{1}<i_{2}<\cdots<i_{g}\) and \(j_{1}<j_{2}<\cdots<j_{g}\) or \(j_{g}<j_{g-1}<\cdots<j_{1}\) hold ( the latter ordering is required for handling mirror images. ), where \(g=0\) is allowed. We compute \(MCS_{b}(G_{1}(u,C),G_{2}(v,D))\) by the following (see Figure 3):  
\[\text{Procedure }SimpleOuterMCS_{b}(G_{1}(u,C),G_{2}(v,D))\] \[s_{\max}\gets 0\text{;}\] **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**\(C\) is a block and \(g=1\)**then continue**; _/*_ blocks must be preserved */ \(s\gets 0\); **for**\(t=1\)**to**\(g\)**do**\(s\gets s+1+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}\). In the above procedure, the first inner **for** loop takes care of blocks, such as \(C_{1}\), \(C_{4}\), \(D_{1}\) and \(D_{4}\) in Figure 3, whereas the second inner **for** loop takes care of half blocks, such as \(C_{2}\), \(C_{3}\), \(D_{2}\), \(D_{3}\) and \(D_{5}\) in \[X = \{C_{1},\ldots,C_{h_{1}},e_{1},\ldots,e_{h_{2}}\}\]0  
For example, consider an alignment, \(((u_{1},u_{2},u_{3}),(v_{1},v_{2},v_{4}))\), in Figure 3, where all alignments are to be examined in the algorithm. Then, the score of this alignment is given by  
\[X = \{C_{1},\ldots,C_{h_{1}},e_{1},\ldots,e_{h_{2}}\}\]1 Computation of \(MCS_{c}(G_{1}(u),G_{2}(v))\). \(3+MCS_{b}(G_{1}(u_{1},C_{1}),G_{2}(v_{1},D_{1}))+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_{4}))\). \(MCS_{b}(G_{1}(u_{1},C_{1}),G_{2}(v_{1},D_{1}))\) comes via the computation of \(MCS_{c}(G_{1}(u_{1}),G_{2}(v_{1}))\), in which \(BG(X,Y;E)\) is given by \(X=\{C_{1}\}\), \(Y=\{D_{1}\}\), \(E=\{(C_{1},D_{1})\}\), and thus, the maximum weight matching is given by \(w(C_{1},D_{1})=MCS_{b}(G_{1}(u_{1},C_{1}),G_{2}(v_{1},D_{1}))\). In this case, an edge, \(\{v,v_{3}\}\), is removed and then \(v_{3}\) is treated as a vertex on the path connecting \(v_{2}\) and \(v_{4}\) in the outer face. For another example, consider an alignment \(((u_{1}),(v_{1}))\) in the same figure. Then, this alignment is ignored by the **\"if... then...\"** line of the procedure, because a bridge in \(G_{c}\), which would correspond to \(\{u,u_{1}\}\) in \(G_{1}\) and \(\{v,v_{1}\}\) in \(G_{2}\), must not be mapped to an edge in \(C\) or \(D\). However, if both \(\{u,u_{1}\}\) and \(\{v,v_{1}\}\) are bridges, the resulting score would be \(1+MCS_{c}(G_{1}(u_{1}),G_{2}(v_{1}))\). Since the above procedure examines all possible alignments, it may take exponential time. However, we can modify it into a dynamic programming procedure, as shown below, where we omit a subprocedure for handling mirror images, because it is trivial. In this procedure, \(u_{1},u_{2},\ldots,u_{h}\) and \(v_{1},v_{2},\ldots,v_{k}\) are processed from left to right. In the first **for** loop, \(M[s,t]\) stores the size of MCS between \(G_{1}(u_{s})\) and \(G_{2}(v_{t})\) plus one (corresponding to a common edge between \(\{u,u_{s}\}\) and \(\{v,v_{t}\}\)). The double **for** loop computes an optimal alignment.