Covering nearly surface-embedded graphs with a fixed number of balls

DOI10.1007/S00454-014-9594-5MaRDI QIDQ741614zbMATH OpenOpenAlexFDO

Authors Glencora Borradaile, Erin W. Chambers

Publication date 12 September 2014

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.8086

zbMATH Keywords

crossing numbergraph coveringseparatorstopological graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A recent result of Chepoi, Estellon and Vaxes [DCG '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.

Recommendations

• Covering planar graphs with a fixed number of balls
• Long cycles in graphs on a fixed surface
• Packing and covering balls in graphs excluding a minor
• On covering bridged plane triangulations with balls
• On the maximum order of graphs embedded in surfaces

Cites work

• Applications of the crossing number
• Bounded VC-dimension implies a fractional Helly theorem
• Covering planar graphs with a fixed number of balls
• Edge Separators of Planar and Outerplanar Graphs With Applications
• Finding small simple cycle separators for 2-connected planar graphs
• Graph minors. XVI: Excluding a non-planar graph
• Graphs on surfaces
• scientific article; zbMATH DE number 3179262 (Why is no real title available?)
• scientific article; zbMATH DE number 2044937 (Why is no real title available?)
• scientific article; zbMATH DE number 1461253 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Quasi-planar graphs have a linear number of edges
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The crossing number of a graph on a compact 2-manifold
• The number of edges in k-quasi-planar graphs
• The toroidal crossing number of the complete graph

Cited in

(5)

• Packing and covering balls in graphs excluding a minor
• Packing and covering with balls on Busemann surfaces
• On covering bridged plane triangulations with balls
• A story of diameter, radius, and (almost) Helly property
• Covering planar graphs with a fixed number of balls

This page was built for publication: Covering nearly surface-embedded graphs with a fixed number of balls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741614)