A graph $G=(V,E)$ is $��$-hyperbolic if for any four vertices $u,v,w,x$, the two larger of the three distance sums $d(u,v)+d(w,x)$, $d(u,w)+d(v,x)$, and $d(u,x)+d(v,w)$ differ by at most $2��\geq 0$. Recent work shows that many real-world graphs have small hyperbolicity $��$. This paper describes the eccentricity terrain of a $��$-hyperbolic graph. The eccentricity function $e_G(v)=\max\{d(v,u) : u \in V\}$ partitions the vertex set of $G$ into eccentricity layers $C_{k}(G) = \{v \in V : e(v)=rad(G)+k\}$, $k \in \mathbb{N}$, where $rad(G)=\min\{e_G(v): v\in V\}$ is the radius of $G$. The paper studies the eccentricity layers of vertices along shortest paths, identifying such terrain features as hills, plains, valleys, terraces, and plateaus. It introduces the notion of $��$-pseudoconvexity, which implies Gromov's $��$-quasiconvexity, and illustrates the abundance of pseudoconvex sets in $��$-hyperbolic graphs. In particular, it shows that all sets $C_{\leq k}(G)=\{v\in V : e_G(v) \leq rad(G) + k\}$, $k\in \mathbb{N}$, are $(2��-1)$-pseudoconvex. Additionally, several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities. An $O(��|E|)$ time eccentricity approximation $\hat{e}(v)$, for all $v\in V$, is presented that uses distances to two mutually distant vertices and satisfies $e_G(v)-2��\leq \hat{e}(v) \leq {e_G}(v)$. It also shows existence of two eccentricity approximating spanning trees $T$, one constructible in $O(��|E|)$ time and the other in $O(|E|)$ time, which satisfy ${e}_G(v) \leq e_T(v) \leq {e}_G(v)+4��+1$ and ${e}_G(v) \leq e_T(v) \leq {e}_G(v)+6��$, respectively. Thus, the eccentricity terrain of a tree gives a good approximation (up-to an additive error $O(��))$ of the eccentricity terrain of a $��$-hyperbolic graph.

22 pages, 4 figures