Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00579
Visibility Graphs of Anchor Polygons
Hossein Boomari and
Alireza Zarei
Vol. 26, no. 1, pp. 1534, 2022. Regular paper.
Abstract The visibility graph of a polygon corresponds to its internal diagonals and boundary edges. For each vertex on the boundary of the polygon, we have a vertex in this graph and if two vertices of the polygon see each other there is an edge between their corresponding vertices in the graph. Two vertices of a polygon see each other if and only if their connecting line segment completely lies inside the polygon. Recognizing visibility graphs is the problem of deciding whether there is a simple polygon whose visibility graph is isomorphic to a given graph. Another important problem is to reconstruct such a polygon if there is any. These problems are well known and wellstudied, but yet open problems in geometric graphs and computational geometry.
However, they have been solved efficiently for special cases where the target polygon is known to be a tower or a spiral polygon. In this paper, we propose a linear time algorithm to solve these recognizing and reconstruction problems for another type of polygons, named anchor polygons.
This work is licensed under the terms of the CCBY license.

Submitted: August 2016.
Reviewed: January 2021.
Revised: March 2021.
Accepted: November 2021.
Final: December 2021.
Published: January 2022.
Communicated by
Sue Whitesides

Journal Supporters
