On the connectivity of visibility graphs
From MaRDI portal
Publication:715001
DOI10.1007/s00454-012-9446-0zbMath1251.05087arXiv1106.3622MaRDI QIDQ715001
Pavel Valtr, Attila Pór, David R. Wood, Michael S. Payne
Publication date: 15 October 2012
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1106.3622
05C35: Extremal problems in graph theory
05C10: Planar graphs; geometric and topological aspects of graph theory
05C12: Distance in graphs
05C40: Connectivity
05C07: Vertex degrees
Related Items
A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths, Recognition and complexity of point visibility graphs, On the connectivity of visibility graphs, On colouring point visibility graphs, Some results on point visibility graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Every large point set contains many collinear points or an empty pentagon
- On the connectivity of visibility graphs
- Degree sequence conditions for maximally edge-connected graphs depending on the clique number
- Blocking visibility for points in general position
- On the chromatic number of the visibility graph of a set of points in the plane
- On visibility and blockers
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- Degree sequence conditions for equal edge‐connectivity and minimum degree, depending on the clique number
- 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
- Visibility graphs of point sets in the plane
