ON THE EMBEDDING PHASE OF THE HOPCROFT AND TARJAN PLANARITY TESTING ALGORITHM

Authors
MEHLHORN K MUTZEL P
Citation
K. Mehlhorn et P. Mutzel, ON THE EMBEDDING PHASE OF THE HOPCROFT AND TARJAN PLANARITY TESTING ALGORITHM, Algorithmica, 16(2), 1996, pp. 233-242
Citations number
15
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
16
Issue
2
Year of publication
1996
Pages
233 - 242
Database
ISI
SICI code
0178-4617(1996)16:2<233:OTEPOT>2.0.ZU;2-J
Abstract
We give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in li near time. An implementation based on this paper can be found in [MMN] .