Given a simple graph, problem is to check if there is a subgraph homeomorphic to k5 or k3,3, and if there is, output which one is present(k5 or k3,3 or both). I need a reasonably fast algorithm that would work on graphs with 15 vertices in under few minutes. I know that I could check if one of those 2 graphs is contained with Tarjan's algorithm for graph planarity, but I also want to know which one it is.
I am coding in c++ and best solution I have is to take all subsets of edges, but that's very expensive. On the other hand, in my first try I fixed vertices, but than I couldn't handle checking if the subgraph is homeomorphic to k5 ot k3,3. I tried removing 2-degree vertices and connecting the neighbours, but there are still edges that should be ignored and I don't see a way to efficiently remove them.
The most efficient solution is not to look directly for K5 or K3,3 sub-graphs but to try to build a planar embedding of the graph and when it fails then extract the failing sub-graph based upon the part of the embedding that failed.
Hopcroft and Tarjan published the first linear-time planarity testing algorithm in 1974 and the methodology is commonly known "path-addition".
It works by:
In 1976, Evan and Tarjan published a linear-time algorithm using a "vertex-addition" methodology based on a PQ-tree data structure.
In 1984, Williamson extended H&T's algorithm to extract the Kuratowski sub-graphs.
In 2004, Boyer and Myrvold published a linear-time algorithm using an "edge-addition" methodology based on a PC-tree data structure and, in 2007, it was extended to extract a Kuratowski sub-graph.
There are plenty more papers that could be referenced including: Ulric - The left-right planarity test (PDF) and Taylor - Planarity Testing by Path Addition (which both explain more of the mathematics behind H&Ts algorithm and the latter includes source code to generates all possible combinations of planar embeddings).
There are existing C/C++ libraries that implement some these algorithms including: