Balanced line separators of unit disk graphs

DOI10.1016/J.COMGEO.2019.101575MaRDI QIDQ5918796zbMATH OpenOpenAlexFDO

Authors Paz Carmi, Man-Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, 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

balanced separatorcenterpointgeometric intersection graphline separatorunit disk graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• Balanced line separators of unit disk graphs
• Cutting a set of disks by a line with leaving many intact disks in both sides
• Halving balls by a hyperplane in deterministic linear time
• Theory and application of width bounded geometric separators
• Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks

Cites work

• -vertex separator is NP-hard even for 3-regular graphs
• A separator theorem for graphs of bounded genus
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• Approximation algorithms for polynomial-expansion and low-density graphs
• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• Compact and low delay routing labeling scheme for unit disk graphs
• Computing a centerpoint of a finite planar set of points in linear time
• Cutting disjoint disks by straight lines
• Engineering planar separator algorithms
• Finding good approximate vertex and edge partitions is NP-hard
• Finding small simple cycle separators for 2-connected planar graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Geometric Separators and Their Applications to Protein Folding in the HP-Model
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Halving balls in deterministic linear time
• scientific article; zbMATH DE number 741006 (Why is no real title available?)
• MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING
• Near-optimal separators in string graphs
• NP-completeness of the Planar Separator Problems
• Realistic input models for geometric algorithms
• Separator theorems and Turán-type results for planar intersection graphs
• Separators for sphere-packings and nearest neighbor graphs
• Short and simple cycle separators in planar graphs
• Sphere and dot product representations of graphs
• Unions of onions: preprocessing imprecise points for fast onion decomposition
• Unit disk graph recognition is NP-hard

Cited in

(7)

• Halving balls in deterministic linear time
• Sublinear separators in intersection graphs of convex shapes
• Efficient Point-to-Point Resistance Distance Queries in Large Graphs
• Balanced line separators of unit disk graphs
• Space-efficient algorithms for reachability in directed geometric graphs
• Recognition and proper coloring of unit segment intersection graphs
• Shortest path separators in unit disk graphs

This page was built for publication: Balanced line separators of unit disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918796)