optimizationgraph-theorycliqueplanar-graphclique-problem

Finding subgraphs homeomorphic to k5 or k3,3


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.


Solution

  • 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.

    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: