Xref: utzoo sci.math:6342 comp.graphics:5220
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!cmcl2!husc6!xait!jane
From: jane@XAIT.Xerox.COM (Jane Eisenstein)
Newsgroups: sci.math,comp.graphics
Subject: embedding planar graphs
Message-ID: <43679@XAIT.Xerox.COM>
Date: 10 Apr 89 17:17:50 GMT
Reply-To: jane@XAIT.Xerox.COM (Jane Eisenstein)
Distribution: na
Organization: Xerox Advanced Information Technology, Cambridge, MA
Lines: 15

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