A characterization of visibility graphs for pseudo-polygons
Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September …, 2015•Springer
In this paper, we give a characterization of the visibility graphs of pseudo-polygons. We first
identify some key combinatorial properties of pseudo-polygons, and we then give a set of
five necessary conditions based off our identified properties. We then prove that these
necessary conditions are also sufficient via a reduction to a characterization of vertex-edge
visibility graphs given by O'Rourke and Streinu.
identify some key combinatorial properties of pseudo-polygons, and we then give a set of
five necessary conditions based off our identified properties. We then prove that these
necessary conditions are also sufficient via a reduction to a characterization of vertex-edge
visibility graphs given by O'Rourke and Streinu.
Abstract
In this paper, we give a characterization of the visibility graphs of pseudo-polygons. We first identify some key combinatorial properties of pseudo-polygons, and we then give a set of five necessary conditions based off our identified properties. We then prove that these necessary conditions are also sufficient via a reduction to a characterization of vertex-edge visibility graphs given by O’Rourke and Streinu.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果