AN APPROACH TO THE SUBGRAPH HOMEOMORPHISM PROBLEM

The subgraph homeomorphism problem for a fixed pattern graph H is stated as follows: given an input graph G equals (V,E), determine whether G has a subgraph homeomorphic to H. We show that the subgraph homeomorphism problem for the fixed graph K//3//,//3 is solvable in polynomial time, where K//3//,//3 is the Thomsen graph, one of the Kuratowski graphs used to characterize planar graphs. Specifically, we present an O( vertical V vertical )-time algorithm for this problem. We also present several pattern graphs for each of which an O( vertical V vertical )-time algorithm exists.