Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!usc!snorkelwacker.mit.edu!ira.uka.de!fauern!forwiss.uni-passau.de!nntpserver!himsolt From: himsolt@trillian.fmi.uni-passau.de (Michael Himsolt) Newsgroups: comp.theory Subject: Re: H-T Planarity Algorithm Message-ID: Date: 14 Feb 91 23:56:07 GMT References: <3441@dali> Sender: usenet@forwiss.uni-passau.de (USENET News System) Organization: University of Passau, Dept. of Mathematics and Computer Science Lines: 28 In-Reply-To: icsrc@ming.cs.montana.edu's message of 6 Feb 91 21:22:49 GMT Nntp-Posting-Host: trillian.fmi.uni-passau.de >>>>> On 6 Feb 91 21:22:49 GMT, icsrc@ming.cs.montana.edu (Rob >>>>> Cimikowski) said: Rob> Does anyone have a source code listing of the Rob> Hopcroft-Tarjan planarity algorithm they could e-mail me? I Rob> would prefer C or Pascal code. We do have an implementation of the HT Planarity Test in C as part of our graph editor GraphEd; it is approx. 800 lines of code. It is not fully tested, but seems to be very stable. We are also trying to add an algorithm to compute (and then draw) a planar embedding. The implementation uses the Sgraph-structure, which is part of GraphEd, so you might need GraphEd, too. GraphEd is available via anonymous ftp from forwiss.uni-passau.de (132.231.1.10). I just put Version 2.03 on the server; it contains the HT-test in the directory graphed2.03/extra/newplanar (the test in graphed2.03/extra/newplanar is quite buggy). Sgraph is in graphed2.03/sgraph (Sgraph algorithms can be run independend of GraphEd, too). Manuals are available from me. -- Michael Himsolt -- Michael Himsolt, Universitaet Passau, Postfach 2540, D-8390 Passau, GERMANY himsolt@fmi.uni-passau.de graphed@fmi.uni-passau.de