Csaba D. Tóth

collaborators

6 papers

cs.CG2026

Improved Euclidean Shallow Light Trees

Hung Le, Shay Solomon, Cuong Than +2

For parameters $α, β \geq 1$ , a spanning tree $T$ of a weighted graph $G$ rooted at a designated vertex $r$ is called an $(α, β)$ -shallow-light tree (SLT) if (i) for every vertex $v$ ,…

cs.CG2026

Geometric $(1 + ε)$ -Spanners with Few Crossings

Kelvin Luu, Csaba D. Tóth

For $n$ points in the plane and $ε > 0$ , we construct a $(1 + ε)$ -spanner with $O (n / ε)$ edges in which every edge has $O ~ (1/ ε^{3})$ crossin…

cs.CG2026

Bichromatic Geometric Spanners

Theodore Fung, Csaba D. Tóth

For an edge-weighted graph $G = (V, E)$ and a stretch parameter $t \geq 1$ , a $t$ -spanner is a subgraph $H \subseteq G$ such that the shortest path distances in $G$ and $H$ satisfy $δ_H…

cs.CG2026

Euclidean Steiner Shallow-Light Trees in Higher Dimensions

Devin Frost, Kimberly Kokado, Csaba D. Tóth

This paper proves a conjecture by Solomon about Steiner shallow-light trees (SLT) in Euclidean $d$ -space: It is shown that for any finite point set $R^{d}$ , any root, and an…

cs.CG2024

Minimum Plane Bichromatic Spanning Trees

Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine +3

For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endp…

cs.CG2024

Towards Instance-Optimal Euclidean Spanners

Hung Le, Shay Solomon, Cuong Than +2

Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic "compactness'' measures of a Euclidean spanner $E$ are the…

Improved Euclidean Shallow Light Trees

Geometric (1+ε)-Spanners with Few Crossings

Bichromatic Geometric Spanners

Euclidean Steiner Shallow-Light Trees in Higher Dimensions

Minimum Plane Bichromatic Spanning Trees

Towards Instance-Optimal Euclidean Spanners

Geometric $(1 + ε)$ -Spanners with Few Crossings