Covering Nearly Surface-Embedded Graphs with a Fixed Number of Balls Public Deposited

Downloadable Content

Download PDF

This is an author's peer-reviewed final manuscript, as accepted by the publisher. The published article is copyrighted by Springer and can be found at:


Attribute NameValues
  • A recent result of Chepoi, Estellon and Vaxes [Disc. Comp. Geom. '07] states that any planar graph of diameter at most 2R can be covered by a constant number of balls of size R; put another way, there are a constant-sized subset of vertices within which every other vertex is distance half the diameter. We generalize this result to graphs embedded on surfaces of fixed genus with a fixed number of apices, making progress toward the conjecture that graphs excluding a fixed minor can also be covered by a constant number of balls. To do so, we develop two tools which may be of independent interest. The first gives a bound on the density of graphs drawn on a surface of genus g having a limit on the number of pairwise-crossing edges. The second bounds the size of a non-contractible cycle in terms of the Euclidean norm of the degree sequence of a graph embedded on surface.
Resource Type
Date Available
Date Issued
  • Borradaile, G., & Chambers, E. W. (2014). Covering nearly surface-embedded graphs with a fixed number of balls. Discrete & Computational Geometry, 51(4), 979-996. doi:10.1007/s00454-014-9594-5
Journal Title
Journal Volume
  • 51
Journal Issue/Number
  • 4
Rights Statement
Funding Statement (additional comments about funding)
  • This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-0963921 and CCF-1054779.
Peer Reviewed



This work has no parents.