An approach to the subgraph homeomorphism problem (Q1062457)

The subgraph homeomorphism problem for a fixed pattern graph H is stated as follows: given an input graph \(G=(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(\(| V|)\)-time algorithm for this problem. This problem was suspected to be NP-complete by \textit{S. Fortune}, \textit{J. Hopcroft} and \textit{J. Wyllie} [ibid. 10, 111-121 (1980; Zbl 0419.05028)]. We also present several pattern graphs for each of which an O(\(| V|)\)-time algorithm exists.