6 papers
Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
Timothy M. Chan, Zhengcheng Huang
In a series of papers, Avraham, Filtser, Kaplan, Katz, and Sharir (SoCG'14), Kaplan, Katz, Saban, and Sharir (ESA'23), and Katz, Saban, and Sharir (ESA'24) studied a class of geome…
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang +2
We present new results on - and -hop spanners for geometric intersection graphs. These include improved upper and lower bounds for - and -hop spanners for many geometri…
Shortest Path Separators in Unit Disk Graphs
Elfarouk Harb, Zhengcheng Huang, Da Wei Zheng
We introduce a new balanced separator theorem for unit-disk graphs involving two shortest paths combined with the 1-hop neighbours of those paths and two other vertices. This answe…
Dynamic Geometric Connectivity in the Plane with Constant Query Time
Timothy M. Chan, Zhengcheng Huang
We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for most types o…
Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size
Timothy M. Chan, Zhengcheng Huang
In SoCG 2022, Conroy and Tóth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an -size 3-hop spanner for dis…
Improved Upper and Lower Bounds for LR Drawings of Binary Trees
Timothy M. Chan, Zhengcheng Huang
In SODA'99, Chan introduced a simple type of planar straight-line upward order-preserving drawings of binary trees, known as LR drawings: such a drawing is obtained by picking a ro…