Stage-graph representations (Q1363763)

Let \(L\) be a segment (called the stage) contained in the \(x\)-axis of the plane and let \(X\) be a set of points in the upper half plane no three of which are collinear. If the graph \(G(x,L)\) has vertex set \(X\) with two vertices adjacent if and only if the infinite line connecting them intersects \(L\), then \(G(x,L)\) is called a plane one-stage ray-shooting graph. If \(L\) is replaced by \(k\) finite closed non-intersecting straight line segments all on the \(x\)-axis then the corresponding graph is said to be represented (via ray-shooting) by \(k\) stages. The paper gives upper and lower bounds on the number of stages needed to represent a graph. In particular every \(n\)-vertex graph can be represented with at most \(\lceil n(n-1)/4 \rceil\) stages and every tree with at most two stages.