Covering Planar Graphs with a Fixed Number of Balls

No abstract is available for this paper.

• Publication year

  2007

• Venue

  Discrete & Computational Geometry

• Publication date

  2007-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00454-006-1260-0
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combinatorial Geometry

  2012cited by this paper
• Bounded VC-Dimension Implies a Fractional Helly Theorem

  2004cited by this paper
• On covering bridged plane triangulations with balls

  2003cited by this paper
• Lectures on discrete geometry

  2002cited by this paper
• Small k-Dominating Sets in Planar Graphs with Applications

  2001influential reference
• Unavoidable Configurations in Complete Topological Graphs

  2000cited by this paper
• Quasi-planar graphs have a linear number of edges

  1995cited by this paper
• Applications of the crossing number

  1994cited by this paper
• Piercing convex sets and the hadwiger-debrunner (p

  1992cited by this paper
• ɛ-nets and simplex range queries

  1987cited by this paper

• Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds

  2026cites this paper
• Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension

  2025cites this paper
• A Tight VC-Dimension Analysis of Clustering Coresets with Applications

  2025cites this paper
• Going Beyond Surfaces in Diameter Approximation

  2025influential citation
• Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs

  2025cites this paper
• Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs

  2025cites this paper
• The Parameterized Complexity of Computing the VC-Dimension

  2025cites this paper
• Efficient Algorithms for Learning Monophonic Halfspaces in Graphs

  2024cites this paper
• Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more

  2024cites this paper
• Practical Computation of Graph VC-Dimension

  2024cites this paper
• Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs

  2024influential citation
• VC Set Systems in Minor-free (Di)Graphs and Applications

  2023influential citation
• Non-Clashing Teaching Maps for Balls in Graphs

  2023cites this paper
• Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs

  2023cites this paper
• Neighborhood Complexity of Planar Graphs

  2023cites this paper
• Obstructions to faster diameter computation: Asteroidal sets

  2022cites this paper
• Sample compression schemes for balls in graphs

  2022cites this paper
• ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION

  2022cites this paper
• Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik-Chervonenkis Dimension

  2022influential citation
• On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs

  2021cites this paper
• Beyond Helly graphs: the diameter problem on absolute retracts

  2021cites this paper
• A story of diameter, radius, and (almost) Helly property

  2020cites this paper
• Packing and Covering Balls in Graphs Excluding a Minor

  2020cites this paper
• A story of diameter, radius and Helly property

  2019cites this paper
• Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension

  2019influential citation
• Algorithms for Discovering Collections of High-Quality and Diverse Solutions, With Applications to Bayesian Non-Negative Matrix Factorization and Reinforcement Learning

  2019cites this paper
• Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension

  2019cites this paper
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs

  2018cites this paper
• Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

  2018cites this paper
• On density of subgraphs of Cartesian products

  2017cites this paper
• Packing and Covering with Balls on Busemann Surfaces

  2017cites this paper
• An Empirical Comparison of Sampling Quality Metrics: A Case Study for Bayesian Nonnegative Matrix Factorization

  2016cites this paper
• Packing and Covering with Balls on Busemann Surfaces

  2015cites this paper
• Covering Nearly Surface-Embedded Graphs with a Fixed Number of Balls

  2014influential citation
• The Degree/Diameter Problem in Maximal Planar Bipartite graphs

  2014cites this paper
• Covering Nearly Surface-Embedded Graphs with a Fixed Number of Balls

  2014influential citation
• VC-dimension and Erdős-Pósa property

  2014influential citation
• Hitting sets: VC-dimension and Multicut. (Hitting sets: VC-dimension et Multicut)

  2013influential citation
• Coloring dense graphs via VC-dimension

  2010cites this paper
• Problems from CGCS Luminy, May 2007

  2010cites this paper
• Packing and covering δ-hyperbolic spaces by balls ?

  2007cites this paper
• Packing and Covering delta -Hyperbolic Spaces by Balls

  2007cites this paper