jane@XAIT.Xerox.COM (Jane Eisenstein) (04/25/89)
Here is a summary of the references that I received in response to my
request for help in modifying the Hopcroft-Tarjan planarity testing
algorithm to create a planar embedding. The first one seems to really
hit the mark. Thanks again to all of the people who sent me papers and
leads.
From doc@dgp.toronto.edu
Tech Report 88-906 from Cornell by Gries and Xue, "The Hopcroft-Tarjan
Planarity Algorithm, Presentations and Improvements" seems to be what
you want. It gives an algorithm which determines if a graph is planar
and if so gives a planar embedding. It supposedly fixes the bugs in the
original H-T algorithm.
From north@ulysses.att.com
My colleague, Phong Vo, has a paper Ranking and Unranking Planar
Embeddings which describes an algorithm that finds the embeddings
(moreover, you give it k and it produces the k-th embedding).
K. P. Vo, W. E. Dick, S. G. Williamson, "Ranking and Unranking Planar
Embeddings", Linear and Multilinear Algebra, 1985, Vol. 18, pp. 35-65.
From mohan@romeo.rpi.edu
I know of a paper which uses the Tarjan algorithm to find the
faces of a solid specified as a graph. The intermediate step involves
finding the planar embedding. I hope it is of help to you. The reference
is :
%A Dutton R.D.
%A Brigham R.C.
%T Efficiently Identifying the Faces of a Solid
%J Computers & Graphics
%V 7
%N 2
%P 143-147
%D 1983
From joel@cs.rochester.edu
1988 35 IEEE Transactions on Circuits and Systems,
Jayakumar & Thulasiraman & Swamy,
"Planar Embedding: Linear-Time Algorithms for Vertex Placement
and Edge Ordering"
1988 15 Annual International Colloquium on Automata, Languages and
Programming,
Tamassia,
"A Dynamic Data Structure for Planar Graph Embedding
(Extended Abstract)"
The latter appears in the Springer-Verlag series Lecture Notes in
Computer Science.