Finding subgraphs homeomorphic to k5 or k3,3

Question

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.

Answer 1

The most efficient solution is not to look directly for K₅ or K_3,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:

• LEDA
• Boost - with an example page for extracting Kuratowski sub-graphs

Answer 2

Maybe SageMath can do something. It has a wrapper for Boyer’s (C) planarity algorithm. The following is a 27-vertex graph for example. It just takes 296 µs in my computer.

sage: G = graphs.SchlaefliGraph()
sage: G.is_planar()
sage: %time s=G.is_planar(kuratowski=True)
sage: s[1]