%0 Conference Proceedings
%T Visibility Graphs of Anchor Polygons
%+ Sharif University of Technology [Tehran] (SUT)
%A Boomari, Hossein
%A Zarei, Alireza
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 1st International Conference on Theoretical Computer Science (TTCS)
%C Tehran, Iran
%Y Mohammed Taghi Hajiaghayi
%Y Mohammad Reza Mousavi
%3 Topics in Theoretical Computer Science
%V LNCS-9541
%P 72-89
%8 2015-08-26
%D 2015
%R 10.1007/978-3-319-28678-5_6
%K Visibility graph
%K Polygon reconstruction
%K Recognizing visibility graph
%K Anchor polygon
%Z Computer Science [cs]Conference papers
%X 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 are well-known and well-studied, but yet open problems in geometric graphs and computational geometry. However, these problems 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 solve these recognizing and reconstruction problems for another type of polygons, named anchor polygons.
%G English
%Z TC 1
%Z WG 1.8
%2 https://inria.hal.science/hal-01446265/document
%2 https://inria.hal.science/hal-01446265/file/385217_1_En_6_Chapter.pdf
%L hal-01446265
%U https://inria.hal.science/hal-01446265
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9541
%~ IFIP-WG1-8
%~ IFIP-TTCS