Recognition and complexity of point visibility graphs
From MaRDI portal
Publication:512262
DOI10.1007/S00454-016-9831-1zbMATH Open1356.05095arXiv1503.07082OpenAlexW2950863166MaRDI QIDQ512262FDOQ512262
Authors: Jean Cardinal, Udo Hoffmann 
Publication date: 24 February 2017
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1503.07082
Recommendations
- Recognition and Complexity of Point Visibility Graphs
- Computational complexity aspects of point visibility graphs
- Point visibility graph recognition is NP-hard
- Some results on point visibility graphs
- Some results on point visibility graphs
- scientific article; zbMATH DE number 4085050
- On recognizing and characterizing visibility graphs of simple polygons
- COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
- scientific article
- Visibility graphs of point sets in the plane
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Oriented Matroids
- On visibility and blockers
- Title not available (Why is that?)
- Computational geometry. Algorithms and applications.
- Title not available (Why is that?)
- Convex Polytopes
- Intersection graphs of segments
- Title not available (Why is that?)
- Title not available (Why is that?)
- Visibility Algorithms in the Plane
- Complexity of some geometric and topological problems
- Title not available (Why is that?)
- Simple realizability of complete abstract topological graphs in P
- Universality theorems for configuration spaces of planar linkages
- Integer realizations of disk and segment graphs
- Some provably hard crossing number problems
- Visibility graphs and oriented matroids
- Some results on point visibility graphs
- Non-stretchable pseudo-visibility graphs
- On the chromatic number of the visibility graph of a set of points in the plane
- Point visibility graph recognition is NP-hard
- The Intrinsic Spread of a Configuration in R d
- On the decidability of Diophantine problems in combinatorial geometry
- Unsolved problems in visibility graphs of points, segments, and polygons
- On recognizing and characterizing visibility graphs of simple polygons
- On the connectivity of visibility graphs
- Universality theorems for inscribed polytopes and Delaunay triangulations
Cited In (23)
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Recognizing Visibility Graphs of Triangulated Irregular Networks
- Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
- On classifying continuous constraint satisfaction problems
- The complexity of the Hausdorff distance
- Two-layer drawings of bipartite graphs
- Computational complexity aspects of point visibility graphs
- On the Complexity of the Planar Slope Number Problem
- On colouring point visibility graphs
- Efficient visibility algorithm for high-frequency time-series: application to fault diagnosis with graph convolutional network
- Some results on point visibility graphs
- A practical algorithm with performance guarantees for the art gallery problem
- The Complexity of Drawing Graphs on Few Lines and Few Planes
- Obstructing Visibilities with One Obstacle
- RAC-Drawability is ∃ℝ-complete and Related Results
- Drawing graphs as spanners
- Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
- COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
- Recognition and Complexity of Point Visibility Graphs
- Bounding and computing obstacle numbers of graphs
- Smoothing the Gap Between NP and ER
- The partial visibility representation extension problem
- 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)
