Carleton University
Technical Report TR-95-06
March 1995
Planar Stage Graphs: Characterizations and Applications
Abstract
We consider combinatorial and algorithmic aspects of the well-known paradigm \killing two birds with one stone”. We de ne a stage graph as follows: vertices are the points from a planar point set, and fu; vg is an edge if and only if the (in nite, straight) line segment joining u to v inter- sects 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 characterization results in a compact linear space representation of stage graphs. This has been exploited for designing improved algorithms for matching in permutation graphs, two processor task scheduling for dependency graphs known to be permutation graphs, and dominance related problems for planar point sets.