Graphs with no 7-wheel subdivision,version II

The subgraph homeomorphism problem, SHP(H), has been shown to be polynomial-time solvable for any fixed pattern graph H, but practical algorithms have been developed only for a few specific pattern graphs. Among these are the wheels with four, five, and six spokes. This paper examines the subgraph homeomorphism problem where the pattern graph is a wheel with seven spokes, and gives a result that describes graphs with no W7-subdivision, showing how they can be built up, using certain operations, from ‘pieces’ of at most 37 vertices. The result leads to an efficient algorithm solving SHP(W7). This algorithm has features that are similar to those in some parameterized algorithms, and may provide useful insight in searching for a fixed-parameter tractable result for SHP(Wk), with parameter k. This technical report is an updated version of Technical Report 2009/239 [10].