Table of Contents

Module: PlanarityTest ./PlanarityTest.py
Imported modules   
from DataStructures import Stack
from copy import deepcopy
from tkMessageBox import showinfo
Functions   
Make_biconnected_graph
PrintGraph
SaveGmlGraph
dfs_in_make_biconnected_graph
dfs_in_reorder
embedding
planarity_test
pt_DFS
reorder
reversal
source
strongly_planar
target
  Make_biconnected_graph 
Make_biconnected_graph ()

We first make it connected by linking all roots of a DFS-forest. 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 DFS-numbers 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 non-bipartite then the segment S(e0) is non-planar. 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

Table of Contents

This document was automatically generated on Fri Mar 15 11:15:02 2002 by HappyDoc version 2.0