Some relations of subsequences in permutations to graph theory with algorithmic applications

Abstract

The representation of some types of graphs as permutations, is utilized in devising efficient algorithms on those graphs. Maximum 'cliques in permutation graphs and circle graphs are found, by searching for a longest ascending or descending subsequence in their representing permutation. The correspondence between n-noded binary trees and the set SSn of stack-sortable permutations, forms the basis of an algorithm for generating and indexing such trees. The-relations between a graph and its representing p ermutation, are also employed in the proof of theorems concerning properties of subsequences in this permutation. In particular, expressions for the average lengths of the longest ascending and descending subsequence a in a random member of SSn , and the average number of inversions in such a permutation, are derived using properties of binary trees. Finally, a correspondence between the set SSn , and the set of permutations of order n With no descending subsequence of length 3, is demonstrated.