A note on visibility graphs (Q1099193): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5615282 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Representing a planar graph by vertical lines joining different levels / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5786239 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on visibility graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3216670 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(87)90190-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2039261795 / rank | |||
Normal rank |
Latest revision as of 11:34, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on visibility graphs |
scientific article |
Statements
A note on visibility graphs (English)
0 references
1987
0 references
Let \(S=\{s_ 1,...,s_ n\}\), \(n\geq 1\), be a set of disjoint vertical straight line segments in a plane. Each \(s_ i\) connects two extreme points \((x_ i,a_ i)\), \((x_ i,b_ i)\), \(a_ i<b_ i\). Assume that \(x_ 1<x_ 2<...<x_ n\) and \(a_ i\neq a_ j\), \(a_ i\neq b_ j\), \(b_ i\neq b_ j\), for \(i\neq j\). We say that \(s_ i\) and \(s_ j\) see each other if there is a horizontal line segment which intersects them, but does not intersect any other line segment between them. A visibility graph G can be constructed on vertices \(v_ 1,...,v_ n\) such that \(v_ i\) and \(v_ j\) are joined by an edge if the corresponding segments \(s_ i\) and \(s_ j\) see each other. It is proved that any visibility graph G can be transformed by successive duplications of existing edges of G into a planar multigraph with all triangular finite faces. Conversely, any such graph is a visibility graph for some set S.
0 references
line segments
0 references
visibility graph
0 references
planar multigraph
0 references