Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!icdoc!qmw-cs!liam From: liam@cs.qmw.ac.uk (William Roberts;) Newsgroups: comp.theory Subject: Re: H-T Planarity Algorithm Message-ID: <2919@redstar.cs.qmw.ac.uk> Date: 18 Feb 91 15:11:19 GMT References: <3441@dali> Sender: usenet@cs.qmw.ac.uk Lines: 37 Nntp-Posting-Host: whitesand 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)