We consider combinatorial and algorithmic aspects of the well-known paradigm "killing two birds with one stone". We define a stage graph as 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 characterization results in a compact linear space representation of stage graphs. This has been exploited for designing improved algorithms for maximum matching in permutation graphs, two processor task scheduling for dependency graphs known to be permutation graphs, and dominance-related problems for planar point sets. We show that a maximum matching in permutation graphs can be computed in Ω(n log2 n) time, where n is the number of vertices. We provide simple optimal sequential and parallel algorithms for several dominance related problems for planar point sets.

Additional Metadata
Journal Theoretical Computer Science
Citation
Bauernöppel, F. (Frank), Kranakis, E, Krizanc, D. (Danny), Maheshwari, A, Sack, J.-R, & Urrutia, J. (Jorge). (1997). Planar stage graphs: Characterizations and applications. Theoretical Computer Science, 175(2), 239–255.