Recognition and complexity of point visibility graphs
From MaRDI portal
(Redirected from Publication:512262)
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)- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Recognizing Visibility Graphs of Triangulated Irregular Networks
- Obstructing visibilities with one obstacle
- Two-layer drawings of bipartite graphs
- Computational complexity aspects of point visibility graphs
- Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
- On classifying continuous constraint satisfaction problems
- The complexity of the Hausdorff distance
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Efficient visibility algorithm for high-frequency time-series: application to fault diagnosis with graph convolutional network
- A practical algorithm with performance guarantees for the art gallery problem
- The Complexity of Drawing Graphs on Few Lines and Few Planes
- Point visibility graph recognition is NP-hard
- Combinatorial properties and recognition of unit square visibility graphs
- RAC-Drawability is ∃ℝ-complete and Related Results
- Drawing graphs as spanners
- COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
- Recognition and Complexity of Point Visibility Graphs
- On the complexity of the planar slope number problem
- Bounding and computing obstacle numbers of graphs
- Smoothing the Gap Between NP and ER
- Coloring polygon visibility graphs and their generalizations
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)
