Carleton University
Technical Report TR-95-07
March 1995
Stage-Graph Representations
Abstract
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 (in nite, 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 xed 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. We study stage representations of stage graphs and give upper and lower bounds on the number of stages needed to represent a graph.