Recognition and complexity of point visibility graphs

DOI10.1007/s00454-016-9831-1zbMath1356.05095arXiv1503.07082OpenAlexW2950863166MaRDI QIDQ512262

Jean Cardinal, Udo Hoffmann

Publication date: 24 February 2017

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

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

zbMATH Keywords

existential theory of the realsgeometric graph representationspoint visibility graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Smoothing the Gap Between NP and ER ⋮ Coloring polygon visibility graphs and their generalizations ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ Two-layer drawings of bipartite graphs ⋮ The complexity of the Hausdorff distance ⋮ Obstructing Visibilities with One Obstacle ⋮ RAC-Drawability is ∃ℝ-complete and Related Results ⋮ On colouring point visibility graphs ⋮ On the Complexity of the Planar Slope Number Problem ⋮ Computational complexity aspects of point visibility graphs ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ Recognizing Visibility Graphs of Triangulated Irregular Networks ⋮ The partial visibility representation extension problem ⋮ Drawing graphs as spanners ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple realizability of complete abstract topological graphs in P
• On recognizing and characterizing visibility graphs of simple polygons
• On the connectivity of visibility graphs
• Universality theorems for inscribed polytopes and Delaunay triangulations
• Some provably hard crossing number problems
• Intersection graphs of segments
• Universality theorems for configuration spaces of planar linkages
• Visibility graphs and oriented matroids
• Integer realizations of disk and segment graphs
• 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
• On visibility and blockers
• The Intrinsic Spread of a Configuration in R d
• Complexity of Some Geometric and Topological Problems
• On the decidability of Diophantine problems in combinatorial geometry
• Convex Polytopes
• Oriented Matroids
• Unsolved problems in visibility graphs of points, segments, and polygons
• Visibility Algorithms in the Plane