Record Details
Covering Nearly Surface-Embedded Graphs with a Fixed Number of Balls
ScholarsArchive at Oregon State University
| Field | Value |
|---|---|
| Title | Covering Nearly Surface-Embedded Graphs with a Fixed Number of Balls |
| Names |
Borradaile, Glencora
(creator) Chambers, Erin Wolf (creator) |
| Date Issued | 2014-06 (iso8601) |
| Note | 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. |
| 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. |
| Genre | Article |
| Topic | Topological graphs |
| Identifier | 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 |
