Article
 

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

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/articles/r207tt972

Descriptions

Attribute NameValues
Creator
Abstract
  • 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.
  • 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: http://link.springer.com/journal/454.
  • Keywords: Graph covering, Crossing number, Separators, Topological graphs
  • Keywords: Graph covering, Crossing number, Separators, Topological graphs
Resource Type
DOI
Date Available
Date Issued
Citation
  • 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.
Publisher
Peer Reviewed
Language
Replaces

Relationships

Parents:

This work has no parents.

Items

Thumbnail Title Date Uploaded Visibility Actions
file details BorradaileGlencoraEECSCoveringNearlySurface.pdf 2017-10-27 Public Download