A note on visibility graphs (Q1099193): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
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 |
Revision as of 16:11, 18 June 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