کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10327306 680970 2005 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Non-stretchable pseudo-visibility graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Non-stretchable pseudo-visibility graphs
چکیده انگلیسی
We exhibit a family of graphs which can be realized as pseudo-visibility graphs of pseudo-polygons, but not of straight-line polygons. The example is based on the characterization of vertex-edge pseudo-visibility graphs of O'Rourke and Streinu [Proc. ACM Symp. Comput. Geometry, Nice, France, 1997, pp. 119-128] and extends a recent result of the author [Proc. ACM Symp. Comput. Geometry, Miami Beach, 1999, pp. 274-280] on non-stretchable vertex-edge visibility graphs. We construct a pseudo-visibility graph for which there exists a unique compatible vertex-edge visibility graph, which is then shown to be non-stretchable. The construction is then extended to an infinite family.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 31, Issue 3, June 2005, Pages 195-206
نویسندگان
,