On the connectivity of visibility graphs

DOI10.1007/S00454-012-9446-0zbMATH Open1251.05087arXiv1106.3622OpenAlexW1963903160MaRDI QIDQ715001FDOQ715001

Authors: Michael S. Payne, Attila Pór, Pavel Valtr, David R. Wood 

Publication date: 15 October 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: 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) <= deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. Furthermore, we find that in visibility graphs every minimum edge cut is the set of edges incident to a vertex of minimum degree. 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, in the case that l=4 we improve this bound to two thirds of the minimum degree.

Full work available at URL: https://arxiv.org/abs/1106.3622

Recommendations

• On the minimum size of visibility graphs
• A tight lower bound on the size of visibility graphs
• Some results on visibility graphs
• On the chromatic number of the visibility graph of a set of points in the plane
• Minimal visibility graphs

zbMATH Keywords

connectivityelliptic curvevisibility graphbivisibility graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• On visibility and blockers
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the chromatic number of the visibility graph of a set of points in the plane
• Title not available (Why is that?)
• Visibility graphs of point sets in the plane
• On the connectivity of visibility graphs
• Blocking visibility for points in general position
• Every large point set contains many collinear points or an empty pentagon
• Degree sequence conditions for maximally edge-connected graphs depending on the clique number
• Degree sequence conditions for equal edge‐connectivity and minimum degree, depending on the clique number
• Title not available (Why is that?)

Cited In (19)

• Recognizing Visibility Graphs of Triangulated Irregular Networks
• Title not available (Why is that?)
• On the minimum size of visibility graphs
• Mutual visibility in graphs
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• On colouring point visibility graphs
• Visibility number of directed graphs
• Title not available (Why is that?)
• Some results on point visibility graphs
• Title not available (Why is that?)
• A note on visibility graphs
• Degree distributions and motif profiles of limited penetrable horizontal visibility graphs
• A visibility graph averaging aggregation operator
• Routing on the Visibility Graph
• Constrained visibility representations of graphs
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• Special subgraphs of weighted visibility graphs
• Recognition and complexity of point visibility graphs
• On the connectivity of visibility graphs

This page was built for publication: On the connectivity of visibility graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715001)