PLANAR STAGE GRAPHS - CHARACTERIZATIONS AND APPLICATIONS

We consider combinatorial and algorithmic aspects of the well-known pa radigm ''killing two birds with one stone''. We define a stage graph a s follows: vertices are points from a planar point set, and {u, v} is an edge if and only if the (infinite, straight) line segment joining u to v intersects a given line segment, called a stage. We show that a graph is a stage graph if and only if it is a permutation graph. The c haracterization results in a compact linear space representation of st age graphs. This has been exploited for designing improved algorithms for maximum matching in permutation graphs, two processor task schedul ing for dependency graphs known to be permutation graphs, and dominanc e-related problems for planar point sets. We show that a maximum match ing in permutation graphs can be computed in Omega(n log(2) n) time, w here n is the number of vertices. We provide simple optimal sequential and parallel algorithms for several dominance related problems for pl anar point sets.