Python, networkx

Question

I need help since I'm not expert in programming.

How can I draw a planar graph (A graph is said to be planar if it can be drawn in the plane such that there are no edge-crossings) for a given graph with n nodes and E edges. and then flip the edges to have another planar graph.( for loop until we get all the possibilities).

Thanks in advance,and I appreciate your help.

PY

---

>>>#visualize with pygraphviz
    A=pgv.AGraph()
    File "<stdin>", line 6
    A=pgv.AGraph()
    ^
    SyntaxError: invalid syntax
>>> A.add_edges_from(G.edges())
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    NameError: name 'A' is not defined
>>> A.layout(prog='dot')
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    NameError: name 'A' is not defined
>>> A.draw('planar.png')
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    NameError: name 'A' is not defined

Answer 1

There are several hard computational problems involved in your question.

First, some theory. If the graph G is planar, then every subgraph of G is planar. Flipping edges from G (that has e edges), would give 2^e-1 planar subgraphs (if we don't care about connectivity), which is exponential (i.e. huge and "bad"). Probably, you'd like to find "maximal" planar subgraphs.

If you'd like to draw planar graphs which also look like planar is computationally hard, i.e. it's one thing to know that there exists a graphical representation where the edges don't cross and another to find such a representation.

To implementation. It seems like networkx doesn't have the function that checks if a graph is planar. Some other packages that work with graphs have (for instance, sage has g.is_planar() function where g is a graph object). Below, I wrote a "naive" (there must be more efficient methods) planarity check with networkx, based on Kuratowski theorem.

import pygraphviz as pgv
import networkx as nx
import itertools as it
from networkx.algorithms import bipartite

def is_planar(G):
    """
    function checks if graph G has K(5) or K(3,3) as minors,
    returns True /False on planarity and nodes of "bad_minor"
    """
    result=True
    bad_minor=[]
    n=len(G.nodes())
    if n>5:
        for subnodes in it.combinations(G.nodes(),6):
            subG=G.subgraph(subnodes)
            if bipartite.is_bipartite(G):# check if the graph G has a subgraph K(3,3)
                X, Y = bipartite.sets(G)
                if len(X)==3:
                    result=False
                    bad_minor=subnodes
    if n>4 and result:
        for subnodes in it.combinations(G.nodes(),5):
            subG=G.subgraph(subnodes)
            if len(subG.edges())==10:# check if the graph G has a subgraph K(5)
                result=False
                bad_minor=subnodes
    return result,bad_minor

#create random planar graph with n nodes and p probability of growing
n=8
p=0.6
while True:
    G=nx.gnp_random_graph(n,p)
    if is_planar(G)[0]:
        break
#visualize with pygraphviz
A=pgv.AGraph()
A.add_edges_from(G.edges())
A.layout(prog='dot')
A.draw('planar.png')

Edit2. If you face troubles with pygraphviz, try to draw with networkx, maybe you find the results ok. So, instead of "visualize with pygraphviz" block try the following:

import matplotlib.pyplot as plt
nx.draw(G)
# comment the line above and uncomment one of the 3 lines below (try each of them):
#nx.draw_random(G)
#nx.draw_circular(G)
#nx.draw_spectral(G)
plt.show()

End of edit2.

The result looks like this.

You see there's one crossing on the picture (but the graph is planar), it's actually a good result (don't forget the problem is computationally hard), pygraphviz is a wrapper to Graphviz which use heuristic algorithms. In the line A.layout(prog='dot') you may try replace 'dot' with 'twopi', 'neato', 'circo' etc to see if you achieve a better visualization.

Edit. Let's also consider your question on planar subgraphs. Let's generate a non-planar graph:

while True:
    J=nx.gnp_random_graph(n,p)
    if is_planar(J)[0]==False:
        break

I think the most efficient way in finding a planar subgraph is to eliminate nodes from the "bad minor" (i.e. K(5) or K(3,3)). Here is my implementation:

def find_planar_subgraph(G):
    if len(G)<3:
        return G
    else:
        is_planar_boolean,bad_minor=is_planar(G)
        if is_planar_boolean:
            return G
        else:
            G.remove_node(bad_minor[0])
            return find_planar_subgraph(G)

Action:

L=find_planar_subgraph(J)
is_planar(L)[0]
>> True

Now you have a planar subgraph L (a networkx graph object) of the non-planar graph G.