Eccentricity terrain of δ-hyperbolic graphs

Abstract 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 ) , d ( u , x ) + d ( v , w ) differ by at most 2 δ ≥ 0 . This paper describes the eccentricity terrain of a δ-hyperbolic graph. The eccentricity function e G ( v ) = max ⁡ { d ( v , u ) : u ∈ V } partitions vertices of G into eccentricity layers C k ( G ) = { v ∈ V : e G ( v ) = r a d ( G ) + k } , k ∈ N , where r a d ( G ) = min ⁡ { e G ( v ) : v ∈ 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. It shows that all sets C ≤ k ( G ) = { v ∈ V : e G ( v ) ≤ r a d ( G ) + k } , k ∈ N , are ( 2 δ − 1 ) -pseudoconvex. Several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities.