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: 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](http://en.wikipedia.org/wiki/Crossing_number_%28graph_theory%29#Complexity),
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](http://www.sagemath.org/) 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](http://en.wikipedia.org/wiki/Kuratowski%27s_theorem#Kuratowski.27s_and_Wagner.27s_theorems).

    
    
    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.![Random planar
graph](http://i.stack.imgur.com/LbIjp.png)

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](http://www.graphviz.org/) 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.

