[sci.math] embedding planar graphs

jane@XAIT.Xerox.COM (Jane Eisenstein) (04/11/89)

I am trying to modify Hopcroft and Tarjan's graph planarity testing
algorithm so that it will produce an embedding of a planar graph in the
plane.  Several authors (including Hopcroft and Tarjan) state that this
is possible.  However, I am having trouble handling the embedding of
special paths.

If you have successfully modified this algorithm to produce embeddings
or can direct me to a description of how it has been done, I'd appreciate
hearing from you.  The only published planar embedding algorithm of
which I am aware is by Chiba et.al. and is not based on the Hopcroft and
Tarjan algorithm.

	Thanks in advance,
		Jane Eisenstein		jane@XAIT.Xerox.COM