Python Library for Boyer-Myrvold planarity test or Kuratowski subgraph identification
Question: I am working with NetworkX Graphs in Python and I would like to find the
Kuratowski subgraphs of any given graph which I have.

The Boyer-Myrvold planar graph testing algorithm can return an existing
Kuratowski subgraph if the graph is not planar (O(n) in the number of vertices
n), so I was hoping that there might already be an implementation of that
algorithm or of a similar algorithm in Python. I have been so far unable to
find one and I am slightly reluctant at having to re-implement it from the
original research paper.

It is even better if it can easily interface with NetworkX library for graphs.


Answer: There is a Python wrapper for part of of John Boyer's planarity code
(<https://code.google.com/p/planarity/>) that might be what you are looking
for. It is at <https://github.com/hagberg/planarity>.

It has a NetworkX interface that allows you to test for planarity and find the
Kurotowski subgraphs if not. e.g.

<https://github.com/hagberg/planarity/blob/master/examples/networkx_interface.py>

    
    
    import planarity
    import networkx as nx
    # Example of the complete graph of 5 nodes, K5
    G=nx.complete_graph(5)
    # K5 is not planar
    print(planarity.is_planar(G)) # False
    # find forbidden Kuratowski subgraph
    K=planarity.kuratowski_subgraph(G)
    print(K.edges()) # K5 edges
    

