Imported modules


from DataStructures import Stack
from copy import deepcopy
from tkMessageBox import showinfo

Functions




Make_biconnected_graph

Make_biconnected_graph ()
We first make it connected by linking all roots of a DFSforest.
Assume now that G is connected.
Let a be any articulation point and let u and v be neighbors
of a belonging to different biconnected components.
Then there are embeddings of the two components with the edges
{u,a} and {v,a} on the boundary of the unbounded face.
Hence we may add the edge {u,v} without destroying planarity.
Proceeding in this way we make G biconnected.


PrintGraph

PrintGraph ( G )


SaveGmlGraph

SaveGmlGraph ( G, fileName )


dfs_in_make_biconnected_graph

dfs_in_make_biconnected_graph ( v )
This procedure determines articulation points and adds appropriate
edges whenever it discovers one.


dfs_in_reorder

dfs_in_reorder ( v )


embedding

embedding (
e0,
t,
T,
A,
)
embed: determine the cycle "C(e0)"
We start by determining the spine cycle.
This is precisley as in strongly_planar.
We also record for the vertices w_r+1, ...,w_k, and w_0 the
incoming cycle edge either in tree_edge_into or in the local
variable back_edge_into_w0.


planarity_test

planarity_test ( Gin )
planarity_test decides whether the InputGraph is planar.
it also order the adjecentLists in counterclockwise.


pt_DFS

pt_DFS ( v )


reorder

reorder ()
The procedure reorder first performs DFS to compute dfsnum, parent
lowpt1 and lowpt2, and the list Del of all forward edges and all
reversals of tree edges.
It then deletes the edges in Del and finally reorders the edges.


reversal

reversal ( e )


source

source ( e )


strongly_planar

strongly_planar ( e0, Att )
We now come to the heart of the planarity test: procedure strongly_planar.
It takes a tree edge e0=(x,y) and tests whether the segment S(e0) is
strongly planar.
If successful it returns (in Att) the ordered list of attachments of S(e0)
(excluding x); high DFSnumbers are at the front of the list.
In alpha it records the placement of the subsegments. strongly_planar operates in three phases.
It first constructs the cycle C(e0) underlying the segment S(e0).
It then constructs the interlacing graph for the segments emanating >from the
spine of the cycle.
If this graph is nonbipartite then the segment S(e0) is nonplanar.
If it is bipartite then the segment is planar.
In this case the third phase checks whether the segment is strongly planar
and, if so, computes its list of attachments.


target

target ( e )

Classes


List  
block 
The constructor takes an edge and a list of attachments and creates

pt_graph  
