Balanced line separators of unit disk graphs

Paz Carmi, Man Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada (Corresponding author), Shakhar Smorodinsky

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of n unit disks in the plane there exists a line ℓ such that ℓ intersects at most O((m+n)log⁡n) disks and each of the halfplanes determined by ℓ contains at most 2n/3 unit disks from the set, where m is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting O(m+n) disks exists, but each halfplane may contain up to 4n/5 disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in n exists when we look at disks of arbitrary radii, even when m=0. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size O(m)).

LanguageEnglish
Article number101575
Number of pages14
JournalComputational Geometry: Theory and Applications
Volume86
DOIs
StatePublished - 1 Jan 2020

Fingerprint

Unit Disk Graph
Separator
Separators
Line
Half-plane
Unit Disk
Intersection Graphs
Intersect
Experimental Evaluation
Linear Time
Radius
Lower bound
Arbitrary
Graph in graph theory
Theorem

Keywords

  • Balanced separator
  • Centerpoint
  • Geometric intersection graph
  • Line separator
  • Unit disk graph

Cite this

Carmi, P., Chiu, M. K., Katz, M. J., Korman, M., Okamoto, Y., van Renssen, A., ... Smorodinsky, S. (2020). Balanced line separators of unit disk graphs. Computational Geometry: Theory and Applications, 86, [101575]. DOI: 10.1016/j.comgeo.2019.101575
Carmi, Paz ; Chiu, Man Kwun ; Katz, Matthew J. ; Korman, Matias ; Okamoto, Yoshio ; van Renssen, André ; Roeloffzen, Marcel ; Shiitada, Taichi ; Smorodinsky, Shakhar. / Balanced line separators of unit disk graphs. In: Computational Geometry: Theory and Applications. 2020 ; Vol. 86.
@article{27bf60569aa54108b12fa9e128f4fab5,
title = "Balanced line separators of unit disk graphs",
abstract = "We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of n unit disks in the plane there exists a line ℓ such that ℓ intersects at most O((m+n)log⁡n) disks and each of the halfplanes determined by ℓ contains at most 2n/3 unit disks from the set, where m is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting O(m+n) disks exists, but each halfplane may contain up to 4n/5 disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in n exists when we look at disks of arbitrary radii, even when m=0. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size O(m)).",
keywords = "Balanced separator, Centerpoint, Geometric intersection graph, Line separator, Unit disk graph",
author = "Paz Carmi and Chiu, {Man Kwun} and Katz, {Matthew J.} and Matias Korman and Yoshio Okamoto and {van Renssen}, Andr{\'e} and Marcel Roeloffzen and Taichi Shiitada and Shakhar Smorodinsky",
year = "2020",
month = "1",
day = "1",
doi = "10.1016/j.comgeo.2019.101575",
language = "English",
volume = "86",
journal = "Computational Geometry",
issn = "0925-7721",
publisher = "Elsevier",

}

Carmi, P, Chiu, MK, Katz, MJ, Korman, M, Okamoto, Y, van Renssen, A, Roeloffzen, M, Shiitada, T & Smorodinsky, S 2020, 'Balanced line separators of unit disk graphs' Computational Geometry: Theory and Applications, vol. 86, 101575. DOI: 10.1016/j.comgeo.2019.101575

Balanced line separators of unit disk graphs. / Carmi, Paz; Chiu, Man Kwun; Katz, Matthew J.; Korman, Matias; Okamoto, Yoshio; van Renssen, André; Roeloffzen, Marcel; Shiitada, Taichi (Corresponding author); Smorodinsky, Shakhar.

In: Computational Geometry: Theory and Applications, Vol. 86, 101575, 01.01.2020.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Balanced line separators of unit disk graphs

AU - Carmi,Paz

AU - Chiu,Man Kwun

AU - Katz,Matthew J.

AU - Korman,Matias

AU - Okamoto,Yoshio

AU - van Renssen,André

AU - Roeloffzen,Marcel

AU - Shiitada,Taichi

AU - Smorodinsky,Shakhar

PY - 2020/1/1

Y1 - 2020/1/1

N2 - We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of n unit disks in the plane there exists a line ℓ such that ℓ intersects at most O((m+n)log⁡n) disks and each of the halfplanes determined by ℓ contains at most 2n/3 unit disks from the set, where m is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting O(m+n) disks exists, but each halfplane may contain up to 4n/5 disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in n exists when we look at disks of arbitrary radii, even when m=0. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size O(m)).

AB - We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of n unit disks in the plane there exists a line ℓ such that ℓ intersects at most O((m+n)log⁡n) disks and each of the halfplanes determined by ℓ contains at most 2n/3 unit disks from the set, where m is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting O(m+n) disks exists, but each halfplane may contain up to 4n/5 disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in n exists when we look at disks of arbitrary radii, even when m=0. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size O(m)).

KW - Balanced separator

KW - Centerpoint

KW - Geometric intersection graph

KW - Line separator

KW - Unit disk graph

UR - http://www.scopus.com/inward/record.url?scp=85072551207&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2019.101575

DO - 10.1016/j.comgeo.2019.101575

M3 - Article

VL - 86

JO - Computational Geometry

T2 - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

M1 - 101575

ER -

Carmi P, Chiu MK, Katz MJ, Korman M, Okamoto Y, van Renssen A et al. Balanced line separators of unit disk graphs. Computational Geometry: Theory and Applications. 2020 Jan 1;86. 101575. Available from, DOI: 10.1016/j.comgeo.2019.101575