
140 CHAPTER 4. PROXIMITY DRAWINGS
d(u, v)
u
v
e
T
(u, v)
Figure 4.16 A (1 + ε)-EMST drawing Γ of a tree with maximum vertex degree 6 for ε =
0.5. For the two highlighted vertices u and v, we have that
d(u,v)
|e
T
(u,v)|
= 0.714 ≥
1
1+ε
= 0.667.
(ii) For every pair of non-adjacent vertices u, v, their proximity region “blown-up” by the
factor (1 + ε
2
) contains some vertices of Γ other than u and v. More formally, let D be a
disk with center c and radius r, and let ε
1
and ε
2
be two nonnegative real numbers. The
ε
1
-shrunk disk of D is the disk centered at c and having radius
r
1+ε
1
; the ε
2
-expanded disk
of D is the disk centered at c and having radius (1 + ε
2
)r. An (