On the Connectivity of Visibility Graphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Connectivity of Visibility Graphs

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

On the Connectivity of Visibility Graphs

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

—

Svazek periodika

48

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

13

Strana od-do

669-681

Kód UT WoS článku

000307507800007

EID výsledku v databázi Scopus

—