The visibility graph of a simple polygon represents visibility relations between its vertices. Knowing the correct order of the vertices around the boundary of a polygon and its visibility graph, it is an open problem to locate the vertices in a plane such that it will be consistent with this visibility graph. This problem has been solved for special cases when we know that the target is a {\it tower}, a {\it spiral}, or an {\it anchor} polygon. Knowing that a given visibility graph belongs to a simple polygon with at most three concave chains on its boundary, a {\it pseudo-triangle}, we propose a linear-time algorithm for reconstructing one of its corresponding polygons. Moreover, we introduce a set of necessary and sufficient properties for characterizing visibility graphs of pseudo-triangles and propose polynomial algorithms for checking these properties.
Mehrpour, S., & Zarei, A. (2024). Pseudo-Triangle Visibility Graph: Characterization and Reconstruction. Scientia Iranica, (), -. doi: 10.24200/sci.2024.63200.8282
MLA
Sahar Mehrpour; Alireza Zarei. "Pseudo-Triangle Visibility Graph: Characterization and Reconstruction". Scientia Iranica, , , 2024, -. doi: 10.24200/sci.2024.63200.8282
HARVARD
Mehrpour, S., Zarei, A. (2024). 'Pseudo-Triangle Visibility Graph: Characterization and Reconstruction', Scientia Iranica, (), pp. -. doi: 10.24200/sci.2024.63200.8282
VANCOUVER
Mehrpour, S., Zarei, A. Pseudo-Triangle Visibility Graph: Characterization and Reconstruction. Scientia Iranica, 2024; (): -. doi: 10.24200/sci.2024.63200.8282
)