🚀 go-pugleaf

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.