Balanced line separators of unit disk graphs

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

zbMATH Keywords

unit disk graphcenterpointgeometric intersection graphbalanced separatorline separator

Mathematics Subject Classification ID

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