STAGE-GRAPH REPRESENTATIONS

We consider graph applications of the well-known paradigm ''killing tw o birds with one stone''. In the plane, this gives rise to a stage gra ph as follows: vertices are the points, and {u, v} is an edge if and o nly if the (infinite, straight) line segment joining u to v intersects the stage. Such graphs are shown to be comparability graphs of ordere d 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 ed ge if and only if the (straight) line segment uv intersects one of the k stages. In this paper, we study stage representations of stage grap hs and give upper and lower bounds on the number of stages needed to r epresent a graph.