Balanced line separators of unit disk graphs
From MaRDI portal
Publication:5918796
DOI10.1016/j.comgeo.2019.101575zbMath1433.68483OpenAlexW2972321504MaRDI QIDQ5918796
Matthew J. Katz, Taichi Shiitada, André van Renssen, Paz Carmi, Marcel Roeloffzen, Man-Kwun Chiu, Matias Korman, Yoshio Okamoto, Shakhar Smorodinsky
Publication date: 22 April 2020
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2019.101575
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Efficient Point-to-Point Resistance Distance Queries in Large Graphs, Space-efficient algorithms for reachability in directed geometric graphs
Cites Work
- Unnamed Item
- Sphere and dot product representations of graphs
- Compact and low delay routing labeling scheme for unit disk graphs
- Separator theorems and Turán-type results for planar intersection graphs
- Finding small simple cycle separators for 2-connected planar graphs
- \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- Finding good approximate vertex and edge partitions is NP-hard
- Computing a centerpoint of a finite planar set of points in linear time
- Unit disk graph recognition is NP-hard
- Realistic input models for geometric algorithms
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Cutting disjoint disks by straight lines
- Halving Balls in Deterministic Linear Time
- [https://portal.mardi4nfdi.de/wiki/Publication:2968106 Unions of Onions: Preprocessing Imprecise Points for Fast Onion Decomposition]
- A separator theorem for graphs of bounded genus
- Geometric Separators and Their Applications to Protein Folding in the HP-Model
- MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- Separators for sphere-packings and nearest neighbor graphs
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Short and Simple Cycle Separators in Planar Graphs
- NP-completeness of the Planar Separator Problems
- Engineering planar separator algorithms
- Near-Optimal Separators in String Graphs