icsrc@ming.cs.montana.edu (Rob Cimikowski) (02/07/91)
Does anyone have a source code listing of the Hopcroft-Tarjan planarity algorithm they could e-mail me? I would prefer C or Pascal code. icsrc@cs.montana.edu
zinkv@azu22.informatik.uni-stuttgart.de (Volker Zink) (02/07/91)
In article <3441@dali> icsrc@ming.cs.montana.edu (Rob Cimikowski) writes: > >Does anyone have a source code listing of the Hopcroft-Tarjan planarity >algorithm they could e-mail me? I would prefer C or Pascal code. > >icsrc@cs.montana.edu I also would appreciate, if someone could send me the source code for this algorithm. Bye... Volker -- --------------------------------------------------------------------------- Volker Zink Email: zinkv@azu.informatik.uni-stuttgart.dbp.de Student local: zinkv@azu Universitaet Stuttgart
kpv@ulysses.att.com (Phong Vo[drew]) (02/10/91)
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.
himsolt@trillian.fmi.uni-passau.de (Michael Himsolt) (02/15/91)
>>>>> 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
liam@cs.qmw.ac.uk (William Roberts;) (02/18/91)
I haven't been able to find my C code for the H-T algorithm, but I do now have the references to other related work. T. Chiba, I. Nishioka & I. Shirakawa, "An Algorithm of maximal planarization of graphs", Proceedings of ISCAS, pp 649-652, July 1979 Describes a modification of the H-T test which produces a planar component of a graph in O(v*E) time and space. Tests the graph until a frond is found which makes the graph non-planar, then breaks that frond and tries again. They have a clever data structure to save some of the information from previous parts of the test; this improves running time but not theoretical efficiency. T. Ozawa & H. Takahashi, Graph Theory and Applications, 108, pp 95-107, Springer Verlag, 1981 Planarisation algorithm (based on PQ-trees) requiring O(V*(V+E)) time. They give statistical results to show that the algorithm performs well on random graphs and argue that the PQ-tree approach is better than H-T because it offers a strightforward way of finding good planar subgraphs. K.S. Booth & G.S. Lueker, "Testing for the Consecutive Ones Property, Interval Graphs and Graph Planarity using PQ-Tree Algorithms", J.Comp.Sys.Sci, vol 13, pp 335-379, 1976. Describes the PQ-tree data structure and its use in graph planarity testing. -- William Roberts ARPA: liam@cs.qmw.ac.uk Queen Mary & Westfield College UUCP: liam@qmw-cs.UUCP Mile End Road AppleLink: UK0087 LONDON, E1 4NS, UK Tel: 071-975 5250 (Fax: 081-980 6533)