کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414768 681033 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximate proximity drawings
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Approximate proximity drawings
چکیده انگلیسی

We introduce and study a generalization of the well-known region of influence proximity drawings, called (ε1,ε2)(ε1,ε2)-proximity drawings  . Intuitively, given a definition of proximity and two real numbers ε1⩾0ε1⩾0 and ε2⩾0ε2⩾0, an (ε1,ε2)(ε1,ε2)-proximity drawing of a graph is a planar straight-line drawing Γ such that: (i) for every pair of adjacent vertices u, v  , their proximity region “shrunk” by the multiplicative factor 11+ε1 does not contain any vertices of Γ; (ii) for every pair of non-adjacent vertices u, v  , their proximity region “expanded” by the factor (1+ε2)(1+ε2) contains some vertices of Γ other than u and v. In particular, the locations of the vertices in such a drawing do not always completely determine which edges must be present/absent, giving us some freedom of choice. We show that this generalization significantly enlarges the family of representable planar graphs for relevant definitions of proximity drawings, including Gabriel drawings, Delaunay drawings, and β  -drawings, even for arbitrarily small values of ε1ε1 and ε2ε2. We also study the extremal case of (0,ε2)(0,ε2)-proximity drawings, which generalize the well-known weak proximity drawing paradigm.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 6, August 2013, Pages 604–614
نویسندگان
, , , , , ,