A chain of a set P of n points in the plane is a
chain of the dominance order on~P. A k-chain is a
subset C of P that can be covered by k chains. A
k-chain C is a maximum k-chain if no other
k-chain contains more elements than C. This paper
deals with the problem of finding a maximum k-chain
of P. Recently, Lou Sarrafzadeh and Lee proposed
algorithms to compute maximum 2- and 3-chains in
optimal time O(nlog n). Using the skeleton S(P) of
a point set P introduced by Viennot we describe a
fairly simple algorithm that computes maximum k-chains
in time O(knlog n) using O(kn) space. The basic
idea is, that the canonical chain partition of a
maximum (k-1)-chain in S(P) provides k regions in
the plane, such that, a maximum k-chain for P can
be obtained as the union of maximal chains in these
regions. If our theorems on skeletons are added to
Viennot's results, they allow to derive the full
Greene-Kleitman theory for permutations from properties
of skeletons.
