Stage-graph representations

DOI10.1016/S0166-218X(96)00080-7MaRDI QIDQ1363763zbMATH OpenOpenAlexFDO

Authors Evangelos Kranakis, D. Krizanc, Anil Maheshwari, Marc Noy, Jörg-Rüdiger Sack, J. Urrutia

Publication date 29 January 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

comparability graphs stage graph

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

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.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Stage-graph representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363763)