1995/09/01 by Yaw-Ling Lin, Steven Skiena · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Robotic Path Planning Algorithms #Visibility graph #Combinatorics #Visibility polygon #Visibility #Mathematics #Pathwidth #Vertex (graph theory) #Discrete mathematics #Polygon (computer graphics) #Indifference graph #Maximal independent set #Planar graph #Outerplanar graph #Vertex cover #1-planar graph #Time complexity #Graph #Chordal graph #Simple polygon #Computer science #Line graph #Regular polygon #Geometry #Optics
paper · doi:10.1142/s0218195995000179
openalex publication_date 1995/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
In this paper, we consider two distinct problems related to complexity aspects of the visibility graphs of simple polygons. Recognizing visibility graphs is a long-standing open problem. It is not even known whether visibility graph recognition is in NP. That visibility graph recognition is in NP would be established if we could demonstrate that any n vertex visibility graph is realized by a polygon which can be drawn on an exponentially-sized grid. This motivates a study of the area requirements for realizing visibility graphs. In this paper, we prove: • Θ(n 3 ) area is necessary and sufficient to realize the complete visibility graph K n . • There exist visibility graphs which require exponential area to realize. • Any maximal outerplanar graph of diameter d can be realized in O(d 2 · 2 d ) area, which can be as small as O(n log 2 n) for a balanced mop. Linear maximal outer-planar graphs can be realized in O(n 8 ) area. The second part of this paper considers the complexity of specific optimization problems on visibility graphs. Given a polygon P, we show that finding a maximum independent set, minimum vertex cover, or maximum dominating set in the visibility graph of P are all NP-complete. Further we show that for polygons P 1 and P 2 , the problem of testing if they have isomorphic visibility graphs is isomorphism-complete. These problems remain hard when given the visibility graphs as input.