Revising the Fellows-Kaschube $K_{3,3}$ Search

Abstract

The first algorithm to achieve linear-time performance searching for and identifying a subgraph homeomorphic to $K_{3,3}$ is due to Fellows and Kaschube. Part of the proof of correctness depends on three cases of a straddling bridge of a subgraph homeomorphic to $K_5$ in an input graph. This paper presents a missing fourth case and revises the algorithm with an additional $K_{3,3}$ homeomorph isolator for the condition corresponding to the missing case. This paper also discusses why the prior proof of correctness missed the fourth case and presents a new proof of correctness showing that there are no other missing cases.