An Efficient Planarity Algorithm |
Other editions - View all
Common terms and phrases
added adjacency structure ALEFT ancestor applied articulation point assume BEGIN biconnected biconnected graph branch called colored complete Computer connected components Consider construct contains Conversely corresponding Definition delete dependency graph dependency subgraph depth-first search descendant determine directed graph discovered edges EDGESTACK ELINK embedding examined exists extension method Figure FIND finish follows formed frond given gives graph G HEAD ILINK illustrated induction initial cycle INSTACK INTEGER INTEGER ARRAY INTEGER VALUE LAST least Lemma Let G linear lowest LOWPT1(v LOWPT2 normal path NUMBER palm tree path P₁ placed planar graph planarity algorithm plane POINT possible presented PROCEDURE Proof properties prove reached relation removed requires result root shows side simple SORT space spanning tree special path STACK statement step subtrees Suppose Theorem Theory traversed triconnected types undirected VARIABLES vertex vertices