Opening book details…
Can I read Non-Existence of Annular Separators in Geometric Graphs on EtoBox?
Non-Existence of Annular Separators in Geometric Graphs by Farzam Ebrahimnejad; James R. Lee is a Computer Science article available to read on EtoBox.
What is Non-Existence of Annular Separators in Geometric Graphs about?
showed that planar graphs with uniform polynomial volume growth admit 1-dimensional annular separators: The vertices at graph distance R from any vertex can be separated from those at distance 2R by removing at most O(R) vertices. They asked whether geometric d-dimensional graphs with uniform polynomial volume growth similarly admit (d -1)-dimensional annular separators when d > 2. We show that this fails in a strong sense: For any d ≥ 3 and every s ≥ 1, there is a collection of interior-disjoint spheres in R d whose tangency graph G has uniform polynomial growth, but such that all annular separators in G have cardinality at least R s .
Who reads Non-Existence of Annular Separators in Geometric Graphs?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Farzam Ebrahimnejad; James R. Lee
- Publisher
- Springer Science and Business Media LLC
- Published
- 2023
- Language
- EN
- Field
- Computer Science (Physical Sciences)