Showing 2024Show all
2 papers · 1 filter
cs.CG2024
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…
cs.CG2024
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…