部分グラフ同型性判定問題は 2 つのグラフ G と H が与えられたとき，G を H に埋め込めるかどうかを判定する問題である．この問題は，ハミルトンパス問題や最大クリーク問題など多くの NP-完全な問題を含んでいるため，一般のグラフ上だけでなく，二つのグラフを連結な平面グラフに制限しても NP-完全である．本論文では，ハミルトンパス問題や最大クリーク問題，同型性判定問題を多項式時間で解くことができるグラフクラス上の部分グラフ同型性判定問題を扱う．具体的には，真区間グラフ (Proper interval graphs)，準閾値グラフ (Trivially perfect graphs)，二部置換グラフ (Bipartite permutation graphs) 上の部分グラフ同型性判定問題が NP-完全であることを示す．また，これらのグラフクラスの部分クラスである補鎖グラフ (Co-chain graphs)，鎖グラフ (Chain graphs)，閾値グラフ (Threshold graphs) に対し，多項式時間アルゴリズムを提案する．The subgraph isomorphism problem is to determine whether a graph isisomorphic to a subgraph of another graph. Since it includes the Hamiltonian path problem, the subgraph isomorphism problem is NP-complete even if the input graphs are connected plannar graphs. In this paper, we deal with proper interval graphs, trivially perfect graphs, and bipartite permutation graphs, and their subclasses. We know that on these graphs Hamiltonian path, maximum clique, and isomorphism problems can be solved in polynomial time. We show that the subgraph isomorpshim is NP-complete even when both of given graphs are connected proper interval graphs, trivially perfect graphs, and bipartite permutation graphs. Then, we propose polynomial time algorithms for the subgraph isomorphism problem on co-chain graphs, chain graphs, and threshold graphs.