Stage-graph representations
type: Item
instance of: scholarly article
title: Stage-graph representations
zbMATH Open document ID: 0879.05068
DOI: 10.1016/S0166-218X(96)00080-7
author: Evangelos Kranakis
author: D. Krizanc
author: Anil Maheshwari
author: Marc Noy
author: Jörg-Rüdiger Sack
author: J. Urrutia
published in: Discrete Applied Mathematics
publication date: 1998-01-29T00:00:00Z
full work available at URL: dam
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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1047183
zbMATH Keywords: stage graph
zbMATH Keywords: comparability graphs
reviewed by: E. Keith Lloyd
MaRDI profile type: Publication
cites work: Optimal shooting: Characterizations and applications
cites work: Q3852212
cites work: The complexity of comparability graph recognition and coloring
cites work: Q3669422
cites work: Parallel concepts in graph theory
cites work: Q3880849
cites work: Q4103565
cites work: Transitive Orientation of Graphs and Identification of Permutation Graphs
cites work: Q5599564
cites work: Regular Graphs with Given Girth and Restricted Circuits
cites work: Q5543323
cites work: On Comparability and Permutation Graphs
cites work: Q4002255
cites work: Q4775880
cites work: Lower Bounds for Approximation by Nonlinear Manifolds
OpenAlex ID: W2167356980
description: scientific article; zbMATH DE number 1047183