## 1 Introduction  
Finding common parts of graph-structured data is an important and fundamental task in computer science. Among many such problems, the _maximum common subgraph problem_ has applications in various areas, which include pattern recognition [1, 2] and chemistry [3, 4]. Although there are several variants, the maximum common subgraph problem (MCS) usually means the problem of finding a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input undirected graphs (_i.e._, the maximum common connected edge subgraph problem).  
Because of its importance in pattern recognition and chemistry, many practical algorithms have been developed for MCS and its variants [1; 2; 3; 4]. Some exponential-time algorithms that are better than naive ones have also been developed [5; 6]. [PERSON] studied the approximability of MCS and related problems [7].  
It is also important for MCS to study a polynomially solvable subclasses of graphs, because graph structures are restricted in many application areas. It is well-known that if input graphs are trees, MCS can be solved in polynomial time using maximum weight bipartite matching [8]. [PERSON] showed that MCS can be solved in polynomial time if input graphs are almost trees of bounded degree, whereas MCS remains NP-hard for almost trees of unbounded degree [9], where a graph is called an almost tree if it is connected and the number of edges in each biconnected component is bounded by the number of vertices plus some constant. [PERSON] _et al_. developed a polynomial-time algorithm for MCS and the maximum common induced connected subgraph problem for a degree bounded partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees, where \(k\) is a constant [10]. However, the latter condition seems rather artificial. [PERSON] _et al_. developed a polynomial-time algorithm for outerplanar graphs under the block-and-bridge preserving subgraph isomorphism [11]. However, they modified the definition of MCS by this restriction. Although it was announced that MCS can be solved in polynomial time if input graphs are partial \(k\)-trees and MCS must be \(k\)-connected (for example, see [12]), the restriction that subgraphs are \(k\)-connected is too strict from a practical viewpoint. As for the subgraph isomorphism problem, which is closely related to MCS, polynomial-time algorithms have been developed for biconnected outerplanar graphs [13; 14] and for partial \(k\)-trees with some constraints, as well as their extensions [15; 16].  
In this paper, we present a polynomial-time algorithm for outerplanar graphs of a bounded degree (a preliminary version has appeared in [17]). Although this graph class is not a superset of the classes in previous studies [9; 10], it covers a wide range of chemical compounds (it was reported that 94.4% of chemical compounds in the NCI database have outerplanar graph structures [18]). Furthermore, the algorithm and its analysis in this paper are not simple extensions or variants of those for the subgraph isomorphism problem for outerplanar graphs [13; 14] or partial \(k\)-trees [15; 16]. These algorithms heavily depend on the property that each connected component in a subgraph is not decomposed. However, to be discussed in Section 4, connected components from both input graphs can be decomposed in MCS, and considering all decompositions easily leads to exponential-time algorithms. In order to cope with this difficulty, we introduce the concept of a _blade_. The blade and its analysis play a key role in this paper.  
It is to be noted that the number of MCS can be exponential even for trees [19]. Therefore, our proposed algorithm and all polynomial-time algorithms mentioned above are focusing on finding the one of MCS's. It should also be noted that the proposed algorithm is not practical, because the polynomial degree is very high, although it gives a non-trivial theoretical result on the computation of MCS.