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.

Theoretical Computer Science
School of Computer Science

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. doi:10.1016/S0304-3975(96)00201-0