We consider graph applications of the well-known paradigm "killing two birds with one stone". In the plane, this gives rise to a stage graph as follows: vertices are the points, and {u, v} is an edge if and only if the (infinite, straight) line segment joining u to v intersects the stage. Such graphs are shown to be comparability graphs of ordered sets of dimension 2. Similar graphs can be constructed when we have a fixed number k of stages on the plane. In this case, {u, v} is an edge if and only if the (straight) line segment uv intersects one of the k stages. In this paper, we study stage representations of stage graphs and give upper and lower bounds on the number of stages needed to represent a graph.

Additional Metadata
Journal Discrete Applied Mathematics
Citation
Kranakis, E, Krizanc, D. (Danny), Maheshwari, A, Noy, M. (Marc), Sack, J.-R, & Urrutia, J. (Jorge). (1997). Stage-graph representations. Discrete Applied Mathematics, 75(1), 71–80.