Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!att!ulysses!kpv
From: kpv@ulysses.att.com (Phong Vo[drew])
Newsgroups: comp.theory
Subject: Re: H-T Planarity Algorithm
Message-ID: <14290@ulysses.att.com>
Date: 9 Feb 91 20:54:19 GMT
References: <3441@dali> <2905@redstar.cs.qmw.ac.uk>
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 13

In article <2905@redstar.cs.qmw.ac.uk>, liam@cs.qmw.ac.uk (William Roberts;) writes:
> 
> What I do remember, however, is that if you want to planarise the graph rather 
> than just test for planarity, the Hopcoft & Tarjan algorithm isn't as useful 
> as the other major algorithm (can't remember who developed it).
> 
Check out 'Ranking and Unranking Planar Embeddings' (Vo, Dick & Williamson,
Linear and Multilinear Algebra, v.18, 1985). We show there how to implement
H-T algorithm in a way that one can generate all different embeddings of the
graph. In particular, algorithms are provided to generate a particular embedding.
The path-tree structure used in that paper can also be used to determine
triconnectivity and series-parallel graphs (which include outer-planar graphs)
as I showed in other papers in the same journal in 1983.