Covering nearly surface-embedded graphs with a fixed number of balls
From MaRDI portal
Publication:741614
DOI10.1007/s00454-014-9594-5zbMath1297.05055arXiv1403.8086OpenAlexW2023651302MaRDI QIDQ741614
Erin Wolf Chambers, Glencora Borradaile
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
Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12)
Related Items
Packing and covering with balls on Busemann surfaces, A story of diameter, radius, and (almost) Helly property, Packing and covering balls in graphs excluding a minor
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Covering planar graphs with a fixed number of balls
- New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
- Finding small simple cycle separators for 2-connected planar graphs
- The crossing number of a graph on a compact 2-manifold
- Quasi-planar graphs have a linear number of edges
- Graph minors. XVI: Excluding a non-planar graph
- Bounded VC-dimension implies a fractional Helly theorem
- Applications of the crossing number
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Edge Separators of Planar and Outerplanar Graphs With Applications
- The Number of Edges in $k$-Quasi-planar Graphs
- SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
- The toroidal crossing number of the complete graph
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
