Unsolved problems in visibility graphs of points, segments, and polygons

2013/11/01 by Subir Kumar Ghosh, Partha P. Goswami · 1 citation
Computer Science · #Computational Geometry and Mesh Generation #Robotic Path Planning Algorithms #Optimization and Search Problems

paper · doi:10.1145/2543581.2543589

openalex publication_date 2013/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

Abstract

In this survey article, we present open problems and conjectures on visibility graphs of points, segments, and polygons along with necessary backgrounds for understanding them.

Citations

• Sets with No Empty Convex 7-Gons
• On a Problem of Formal Logic
• Sur le coloriage des graphs
• A threshold of ln n for approximating set cover
• Every Large Point Set contains Many Collinear Points or an Empty Pentagon
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

Cited by

• Big-line-big-clique conjecture [wikipedia]