Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
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 Plesn'ik (1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesn'ik by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)
Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes
,