## 4 Algorithm for Outerplanar Graphs of Bounded Degree  
In order to extend the algorithm in Section 3 for a general (but bounded degree) case, we need to consider the decomposition of biconnected components. For example, consider graphs \(G_{1}\) and \(G_{2}\) in Figure 5. We can see that in order to obtain a maximum common subgraph, biconnected components in \(G_{1}\) and \(G_{2}\) should be decomposed, as shown in Figure 5, where there can be multiple ways of optimal decompositions in general. This is the crucial point, because considering all possible decompositions easily leads to exponential-time algorithms. In order to characterize decomposed components, we introduce the concept of a _blade_, as shown below (see also Figure 6). Suppose that \(v_{i_{1}},\ldots,v_{i_{k}}\) are the vertices of a half block arranged in this order, and \(v_{i_{1}}\) and \(v_{i_{k}}\) are respectively connected to \(v\) and \(v^{\prime}\), where \(v\) and \(v^{\prime}\) can be the same vertex. If we cut one edge, \(\{v_{i_{k}},v_{i_{k+1}}\}\) for \(i_{h}\in\{2,3,...,k-2\}\), we obtain two half blocks, one induced by \(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{h}}\) and the other induced by \(v_{i_{k}},v_{i_{k-1}},\ldots,v_{i_{h+1}}\). However, only one half block is obtained in the case of \(i_{1}=i_{h}\) or \(i_{k}=i_{h+1}\), and no half block is obtained in the case of \(k=2\) (see Figure 7). Each of these half blocks is a chain of biconnected components called a _blade body_, and a subgraph consisting of a blade body and itsdescendants is called a _blade_. Vertices \(v_{i_{1}}\) and \(v_{i_{k}}\), an edge \(\{v_{i_{h}},v_{i_{h+1}}\}\) and vertices \(v_{i_{h}},v_{i_{h+1}}\) are called _base vertices_, a _tip edge_ and _tip vertices_, respectively. The sequence of edges in the shortest path from \(v_{i_{1}}\) to \(v_{i_{h}}\) (resp. from \(v_{i_{k}}\) to \(v_{i_{h+1}}\)) is called the _backbone_ of a blade. As a result, the edges between two blades are deleted (it does not cause a problem, because all possible configurations are examined, as discussed later). In addition, there exists three subcases, depending on the existence of edges \(\{v_{i_{1}},v_{i_{k}}\}\) and \(\{v^{\prime},v_{i_{1}}\}\) (cases with \(\{v,v_{i_{k}}\}\) can be handled in an analogous way). We need not consider the case where \(\{v^{\prime},v_{i_{1}}\}\) is deleted, but \(\{v_{i_{1}},v_{i_{k}}\}\) remains, because deletion of \(\{v^{\prime},v_{i_{1}}\}\) can be handled in the computation of \(MCS_{p}(G_{1}(u,u^{\prime}),G_{2}(v,v^{\prime}))\)):  
* both \(\{v_{i_{1}},v_{i_{k}}\}\) and \(\{v^{\prime},v_{i_{1}}\}\) are deleted
* \(\{v_{i_{1}},v_{i_{k}}\}\) is deleted, but \(\{v^{\prime},v_{i_{1}}\}\) remains
* both \(\{v_{i_{1}},v_{i_{k}}\}\) and \(\{v^{\prime},v_{i_{1}}\}\) remain  
where these three cases are respectively denoted by \"deletion of \(e\)\", \"deletion of \(\overline{e}\)\" and \"deletion of \(\hat{e}\)\" (see Figure 7). It is to be noted that, in any case, we cannot have multiple tip edges simultaneously for the same pair, \((v,v^{\prime})\), because disconnected component(s) would appear if multiple tip edges exist. Figure 5: Example of a difficult case. Figure 6: (**A**) Construction of blades where subgraphs, excluding gray regions (descendant components), are blade bodies; and (**B**) schematic illustration of a blade. In addition, we allow \(\{v,v_{i_{1}}\}\) (resp. \(\{v^{\prime},v_{i_{k}}\}\)) to be a tip edge. In this case, after removing this tip edge, the resulting half block induced by \(v_{i_{k}},\ldots,v_{i_{2}},v_{i_{1}}\) (resp. \((v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k}})\)) is a blade body, where \(v_{i_{k}}\) (resp. \(v_{i_{1}}\)) becomes the base vertex. For example, the rightmost blade in Figure 8 is created by removing a tip edge \(\{u,u_{5}\}\) and \(u_{4}\) becomes the base vertex. Since a blade can be specified by a pair of base and tip vertices and an orientation (clockwise or counterclockwise), there exist \(O(n^{2})\) blades in \(G_{1}\) and \(G_{2}\).