On the Connectivity of Visibility Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10127501" target="_blank" >RIV/00216208:11320/12:10127501 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s00454-012-9446-0" target="_blank" >http://dx.doi.org/10.1007/s00454-012-9446-0</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00454-012-9446-0" target="_blank" >10.1007/s00454-012-9446-0</a>
Alternative languages
Result language
angličtina
Original language name
On the Connectivity of Visibility Graphs
Original language description
The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesnik (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71-93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesnik by showing that for any two vertices v and w in a graph of diameter 2, if deg(v) is smaller or equal deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most l collinear vertices has connectivity at least n-1/l-1, which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, i
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Discrete and Computational Geometry
ISSN
0179-5376
e-ISSN
—
Volume of the periodical
48
Issue of the periodical within the volume
3
Country of publishing house
DE - GERMANY
Number of pages
13
Pages from-to
669-681
UT code for WoS article
000307507800007
EID of the result in the Scopus database
—