A fast 0(n) Embedding Algorithm, based on the HopcroftTarjan Planary Test
Mutzel, Petra
(1992)
A fast 0(n) Embedding Algorithm, based on the HopcroftTarjan Planary Test.
Technical Report
, 26 p.
Abstract
The embedding problem for a planar undirected graph G = (V,E) consists of constructing adjacency lists A(v) for each node v in V, in which all the neighbors of v appear in clockwise order with respect to a planar drawing of G. Such a set of adjacency lists is called a (combinatorial) embedding of G. Chiba presented a linear time algorithm based on the 'vertexaddition' planarity testing algorithm of Lempel, Even and Cederbaum using a PQtree. It is very complicated to implement this data structure. He also pointed out that it is fairly complicated to modify the linear 'pathaddition' planarity testing algorithm of Hopcroft and Tarjan, such that it produces an embedding. We present a straightforward extension of the Hopcroft and Tarjan planarity testing algorithm which is easy to implement. Our method runs in linear time and performs very efficiently in practice.
Download: 
Postscript
Download (572kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  No citation data. 
Uncontrolled Keywords:  embeddings graph theory planar graphs planarity testing topological embeddings 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  zpr92107 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:46 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/107 