Jonathan Conroy

collaborators

5 papers

cs.DS2026

Cutting Planarians: Planar Emulators for String Graphs

Hsien-Chih Chang, Jonathan Conroy, Zihan Tan +1

In this paper we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane (known as the string graphs) in the constant and $1+\varepsilo…

cs.DS2026

DAG Covers: The Steiner Point Effect

Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4

Given a weighted digraph $G$ , a $(t, g, I^¼)$ -DAG cover is a collection of $g$ dominating DAGs $D_{1}, \dots, D_{g}$ such that all distances are approximately preserved: for every pair $(u,…

cs.CG2026

Dynamic Light Spanners in Doubling Metrics

Sujoy Bhore, Jonathan Conroy, Arnold Filtser

A $t$ -spanner of a point set $X$ in a metric space $(X, I^´)$ is a graph $G$ with vertex set $P$ such that, for any pair of points $u, v \in X$ , the distance between $u$ an…

cs.DS2025

Distance Approximating Minors for Planar and Minor-Free Graphs

Hsien-Chih Chang, Jonathan Conroy

Given an edge-weighted graph $G$ and a subset of vertices $T$ called terminals, an $I^\pm$ -distance-approximating minor ( $I^\pm$ -DAM) of $G$ is a graph minor $H$ of $G$ that contains all…

cs.DS2025

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

Hsien-Chih Chang, Jonathan Conroy, Hung Le +2

A $(1 + ε)$ -stretch tree cover of an edge-weighted $n$ -vertex graph $G$ is a collection of trees, where every pair of vertices has a $(1 + ε)$ -stretch path in one o…