Approximate Proximity DrawingsEvans, William S. and Gansner, Emden R. and Kaufmann, Michael and Liotta, Giuseppe and Meijer, Henk and Spillner, Andreas (2012) Approximate Proximity Drawings. In: Graph Drawing 19th International Symposium, GD 2011, September 2123, 2011 , pp. 166178(Official URL: http://dx.doi.org/10.1007/9783642258787_17). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642258787_17
AbstractWe introduce and study a generalization of the wellknown region of influence proximity drawings, called (ε1,ε2)proximity drawings. Intuitively, given a definition of proximity and two real numbers ε1 ≥ 0 and ε2 ≥ 0, an (ε1,ε2)proximity drawing of a graph is a planar straightline drawing Γ such that: (i) for every pair of adjacent vertices u, v, their proximity region “shrunk” by the multiplicative factor 1:(1+ε1) does not contain any vertices of Γ; (ii) for every pair of nonadjacent vertices u, v, their proximity region “blownup” by the factor (1+ε2) contains some vertices of Γ other than u and v. We show that by using this generalization, we can significantly enlarge the family of the representable planar graphs for relevant definitions of proximity drawings, including Gabriel drawings, Delaunay drawings, and βdrawings, even for arbitrarily small values of ε1 and ε2 . We also study the extremal case of (0,ε2)proximity drawings, which generalizes the wellknown weak proximity drawing model.
Actions (login required)
