2 citations · 4 across the 11 of their papers we have counts for
13 papers
Peeling Half the Onion: Embedding -Outerplanar Graphs into and Trees with a Polynomial Distortion (in )
Hsien-Chih Chang, Jonathan Conroy, William Eliot +2
Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that -outerplanar graphs can be embedded into trees and with distortion . Their result is pe…
DAG Covers for Structured Graphs: The Steiner Point Effect
Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4
Given a weighted digraph , a -DAG cover is a collection of dominating DAGs such that all distances are approximately preserved: for every pair $(u,v…
Dynamic Light Spanners in Doubling Metrics
Sujoy Bhore, Jonathan Conroy, Arnold Filtser
A -spanner of a point set in a metric space is a graph with vertex set such that, for any pair of points , the distance between and…
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…
Distance Approximating Minors for Planar and Minor-Free Graphs
Hsien-Chih Chang, Jonathan Conroy
Given an edge-weighted graph and a subset of vertices called terminals, an -distance-approximating minor (-DAM) of is a graph minor of that contains all t…
Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
Hsien-Chih Chang, Jonathan Conroy, Hung Le +2
A -stretch tree cover of an edge-weighted -vertex graph is a collection of trees, where every pair of vertices has a -stretch path in one o…
Embedding Planar Graphs into Graphs of Treewidth
Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy +3
Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected distortion of -vertex planar graphs (with polynomial…
Optimal Euclidean Tree Covers
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
A of a metric space is a collection of trees, where every pair of points has a -stretch path in one of the trees. The…
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCLMST23], is a new type of graph partition into low-diameter clusters. R…
Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
Recently the authors [CCLMST23] introduced the notion of shortcut partition of planar graphs and obtained several results from the partition, including a tree cover with tre…
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of…
Hop-Spanners for Geometric Intersection Graphs
Jonathan B. Conroy, Csaba D. Tóth
A -spanner of a graph is a subgraph that contains a -path of length at most for every . It is known that every -vertex graph admits a $(…
Robot Development and Path Planning for Indoor Ultraviolet Light Disinfection
Jonathan Conroy, Christopher Thierauf, Parker Rule +5
Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many indoor settings as a result of COVID-19, but current robotic systems at…