Search code examples
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.

    • Hopcroft and Tarjan published the first linear-time planarity testing algorithm in 1974 and the methodology is commonly known "path-addition".

      It works by:

      • Using a DFS to separate the graph into bi-connected components.
      • Then for each bi-connected component, ordering the edges into a hierarchy of paths such that the first path of the bi-connected component is a cycle (creating two faces inside and outside the cycle) and then each successive path connects to its parent path and to an ancestor path within the hierarchy;
      • The cycle, trivially, creates two faces within the embedding (inside and outside the cycle) and then each successive path bisects one of the previous faces separating it into two sub-faces.
      • Through maintaining a pair of linked-lists representing left-right (or inside-outside), the algorithm tries to embed each successive path onto the inside face and will check whether this conflicts with the currently embedded paths and either swap the current path or a block of previously embedded paths from the inside to the outside (they never get swapped back from outside to inside).
      • When a path cannot be embedded into either the inside or an outside face then the graph is non-planar.

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