Mutzel, Petra 
ORCID: 0000-0001-7621-971X
(1992).
A fast 0(n) Embedding Algorithm, based on the Hopcroft-Tarjan Planary Test.
["eprint_fieldopt_monograph_type_preprint" not defined].
|
PDF
zpr92-107.pdf Download (313kB) | Preview |
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 'vertex-addition' planarity testing algorithm of Lempel, Even and Cederbaum using a PQ-tree. It is very complicated to implement this data structure. He also pointed out that it is fairly complicated to modify the linear 'path-addition' 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.
| Item Type: | Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined]) | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-546701 | ||||||||
| Date: | 1992 | ||||||||
| Language: | English | ||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||
| Subjects: | Data processing Computer science | ||||||||
| Refereed: | No | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54670 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |