Research Projects

Most of my active research projects are about planar metrics. What property does planar metrics have that makes them special? What advantages can we take to construct better and more efficient algorithms? Can we represent planar metrics in succinct forms, while preserving the distances exactly or approximately?

depth contours
Curves and Graphs on Surfaces

From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy,
with Brittany Terese Fasy, Bradley McCoy, David L. Millman, and Carola Wenk,
WADS 2023.
Untangling Planar Graphs and Curves by Staying Positive,
with Santiago Aranguri and Dylan Fridman,
SODA 2022.
Tightening Curves on Surfaces Monotonically with Applications,
with Arnaud de Mesmay,
SODA 2020.

compressed graph from hierarchical covering
Efficient Optimization in Euclidean Spaces

Optimal Euclidean Tree Covers,
with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
SoCG 2024.
Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching,
with Pankaj Agarwal, Sharath Raghvendra and Allen Xiao,
STOC 2022.
Dynamic Geometric Set Cover and Hitting Set,
with Pankaj Agarwal, Subhash Suri, Allen Xiao, and Jie Xue,
SoCG 2020.

emulator for Monge matrix
Distance-Preserving Structures for Planar Metrics

Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More,
with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
SODA 2024.
Covering Planar Metrics and Beyond by O(1) Trees,
with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than,
FOCS 2023.
Near-Linear ε-Emulators for Planar Graphs,
with Robert Krauthgamer and Zihan Tan,
STOC 2022.

← Back to Main Page

last modified on