Recognition and complexity of point visibility graphs
From MaRDI portal
Abstract: A point visibility graph is a graph induced by a set of points in the plane, where every vertex corresponds to a point, and two vertices are adjacent whenever the two corresponding points are visible from each other, that is, the open segment between them does not contain any other point of the set. We study the recognition problem for point visibility graphs: given a simple undirected graph, decide whether it is the visibility graph of some point set in the plane. We show that the problem is complete for the existential theory of the reals. Hence the problem is as hard as deciding the existence of a real solution to a system of polynomial inequalities. The proof involves simple substructures forcing collinearities in all realizations of some visibility graphs, which are applied to the algebraic universality constructions of Mn"ev and Richter-Gebert. This solves a longstanding open question and paves the way for the analysis of other classes of visibility graphs. Furthermore, as a corollary of one of our construction, we show that there exist point visibility graphs that do not admit any geometric realization with points having integer coordinates.
Recommendations
- Recognition and Complexity of Point Visibility Graphs
- Computational complexity aspects of point visibility graphs
- Point visibility graph recognition is NP-hard
- scientific article; zbMATH DE number 4085050
- On recognizing and characterizing visibility graphs of simple polygons
- COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
- scientific article; zbMATH DE number 5542506
- Visibility graphs of point sets in the plane
Cites work
- scientific article; zbMATH DE number 4065813 (Why is no real title available?)
- scientific article; zbMATH DE number 4092241 (Why is no real title available?)
- scientific article; zbMATH DE number 17663 (Why is no real title available?)
- scientific article; zbMATH DE number 3336816 (Why is no real title available?)
- scientific article; zbMATH DE number 3394958 (Why is no real title available?)
- Complexity of some geometric and topological problems
- Computational geometry. Algorithms and applications.
- Convex Polytopes
- Integer realizations of disk and segment graphs
- Intersection graphs of segments
- Non-stretchable pseudo-visibility graphs
- On recognizing and characterizing visibility graphs of simple polygons
- On the chromatic number of the visibility graph of a set of points in the plane
- On the connectivity of visibility graphs
- On the decidability of Diophantine problems in combinatorial geometry
- On visibility and blockers
- Oriented Matroids
- Point visibility graph recognition is NP-hard
- Simple realizability of complete abstract topological graphs in P
- Some provably hard crossing number problems
- The Intrinsic Spread of a Configuration in R d
- Universality theorems for configuration spaces of planar linkages
- Universality theorems for inscribed polytopes and Delaunay triangulations
- Unsolved problems in visibility graphs of points, segments, and polygons
- Visibility Algorithms in the Plane
- Visibility graphs and oriented matroids
Cited in
(22)- Efficient visibility algorithm for high-frequency time-series: application to fault diagnosis with graph convolutional network
- Recognizing Visibility Graphs of Triangulated Irregular Networks
- Coloring polygon visibility graphs and their generalizations
- RAC-Drawability is ∃ℝ-complete and Related Results
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Obstructing visibilities with one obstacle
- The Complexity of Drawing Graphs on Few Lines and Few Planes
- The complexity of the Hausdorff distance
- Bounding and computing obstacle numbers of graphs
- COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
- Two-layer drawings of bipartite graphs
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Computational complexity aspects of point visibility graphs
- On the complexity of the planar slope number problem
- A practical algorithm with performance guarantees for the art gallery problem
- Combinatorial properties and recognition of unit square visibility graphs
- Drawing graphs as spanners
- Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
- On classifying continuous constraint satisfaction problems
- Smoothing the Gap Between NP and ER
- Point visibility graph recognition is NP-hard
- Recognition and Complexity of Point Visibility Graphs
This page was built for publication: Recognition and complexity of point visibility graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512262)
