EPIC: Support an algorithm to search for a subgraph homeomorphic to K_5

[lichengzhang1]

Hi,
Great software! I noticed the following options:
-2 = Search for subgraph homeomorphic to $K_{2,3}$
-3 = Search for subgraph homeomorphic to $K_{3,3}$
-4 = Search for subgraph homeomorphic to $K_4$

As the subdivision of $K_5$ is also an important subgraph, can it search for a subgraph homeomorphic to $K_5$?

Licheng.

[john-boyer-phd]

Agreed this would be a much-desired addition to the project, and -5 on the command-line and 5 in the menu will be used if/when this does get added (and there's even a defined embed flag in graph.h in anticipation of the eventual development of this algorithm). However, it may be quite a while until this happens because there hasn't yet been much effort nor progress on designing an extension to the edge addition planarity algorithm for this case. Since this project contains a generalized graph library underneath the planarity algorithm, it is also feasible to implement any K₅ homeomorphic subgraph search algorithm, not just a planarity algorithm extension, but unfortunately there aren't any such algorithms yet. The closest I'm aware of is a method by Kezdy and McGuinness, but there are no other implementations of it, no journal paper follow-up to give more details than the SODA conference paper, it has quadratic rather than linear time performance, and it finds K₅ minors (which may not be indicative of a subgraph homeomorphic to K₅).