Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Visibility Graphs of Anchor Polygons
Hossein Boomari and Alireza Zarei
Vol. 26, no. 1, pp. 15-34, 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 well-studied, 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 CC-BY license.
Submitted: August 2016.
Reviewed: January 2021.
Revised: March 2021.
Accepted: November 2021.
Final: December 2021.
Published: January 2022.
Communicated by Sue Whitesides