mcloughlinf@ul.ie (06/12/91)
Hi, a few weeks back I posted a request for some info on PQ-trees and associated algorithms. I got (very) few answers but I got a request for more information from Lou Kates in Univ. of Waterloo. I tried to reply to her but I couldn't get through to that mail address. I've also sent off requests to the postmaster at that address but, again, got no reply. This is therefore a last-ditch attempt at getting through - I'm sorry if I shouldn't be posting this in this newsgroup but this is where she said she got my original posting from. Anyhow, this is my reply: Lou, the article I refer to is "Testing for the consequtive ones property, interval graphs and and graph planarity using PQ-tree algorithms" K.S. Booth and G.S. Leuker, J. Comp. Syst. Sci., vol 13, no 3, pp 335-379, Dec. 1976. In its broadest terms, a PQ-tree is a data structure which can be used to represent permutations in a set. Specifically, " PQ-trees can be used to represent the permutations of a set U in which various subsets of U occur consequtively" [taken from the abstract of the above paper]. In effect, one PQ-tree may represent a class of permutations, not only one such valid permutation. Lempel, Even and Cederbaum in their paper on planarity: "An algorithm for planarity testing of graphs" Theory of Graphs: Int. Symposium, Rome, July '66 describe an algorithm for testing the planarity (surprise, surprise :-) ) of graphs. They base their test on a reduction of a set of graph edges i.e. obtaining a certain permutation of the nodes in a graph in order to determine its planarity (or lack of it). Because the LEC algorithm is based on the ordering of a set of permutations it lent itself to be implemented using PQ-trees and the algorithms associated with them. thanks for your patience, fionbarr. Fionbarr Mc Loughlin mcloughlinf@ul.ie Dept. of Computer Science and Info. Systems, University of Limerick, Rep. of Ireland.