Hung Le

activity

20242026

collaborators

Showing 2026 · cs.DSShow all

2 papers · 2 filters

cs.DS2026

Metric Planarity Testing is Hard

Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak +3

A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for…

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…

Metric Planarity Testing is Hard

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

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