# A fast 0(n) Embedding Algorithm, based on the Hopcroft-Tarjan Planary Test

Mutzel, Petra
(1992)
*A fast 0(n) Embedding Algorithm, based on the Hopcroft-Tarjan 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 '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.

Download: |
Postscript
Download (572kB) | Preview |
---|---|

Export as: | [error in script] |

Editorial actions: |
View Item (Login required) |

ZAIK Number: | [error in script] |
---|---|

Depositing User: | Archive Admin |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 19 Dec 2011 09:46 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/107 |