Jonathan Conroy

activity

20212026

most citedCovering Planar Metrics (and Beyond): O(1) Trees Suffice

2 citations · 4 across the 11 of their papers we have counts for

collaborators

Showing 2026 · cs.DSShow all

2 papers · 2 filters

cs.DS2026

Peeling Half the Onion: Embedding $k$ -Outerplanar Graphs into $ℓ_{1}$ and Trees with a Polynomial Distortion (in $k$ )

Hsien-Chih Chang, Jonathan Conroy, William Eliot +2

Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that $k$ -outerplanar graphs can be embedded into trees and $ℓ_{1}$ with distortion $2^{O (k)}$ . Their result is pe…

cs.DS2026

DAG Covers for Structured Graphs: The Steiner Point Effect

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

Given a weighted digraph $G$ , a $(t, g, μ)$ -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,v…

Peeling Half the Onion: Embedding k-Outerplanar Graphs into ℓ1​ and Trees with a Polynomial Distortion (in k)

DAG Covers for Structured Graphs: The Steiner Point Effect

Peeling Half the Onion: Embedding $k$ -Outerplanar Graphs into $ℓ_{1}$ and Trees with a Polynomial Distortion (in $k$ )