Csaba D. Tóth

activity

20242026

collaborators

Showing 2025Show all

6 papers · 1 filter

cs.CG2025

Approximating Euclidean Shallow-Light Trees

Hung Le, Shay Solomon, Cuong Than +2

For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$ , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum…

cs.CG2025

Online Hitting Set for Axis-Aligned Squares

Minati De, Satyam Singh, Csaba D. Tóth

We are given a set $P$ of $n$ points in the plane, and a sequence of axis-aligned squares that arrive in an online fashion. The online hitting set problem consists of maintaining,…

cs.CG2025

The Price of Connectivity Augmentation on Planar Graphs

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine +5

Given two classes of graphs, $G_{1} \subseteq G_{2}$ , and a $c$ -connected graph $G \in G_{1}$ , we wish to augment $G$ with a smallest cardinality set of new e…

cs.DS2025

Approximate Light Spanners in Planar Graphs

Hung Le, Shay Solomon, Cuong Than +2

In their seminal paper, Althöfer et al. (DCG 1993) introduced the {\em greedy spanner} and showed that, for any weighted planar graph $G$ , the weight of the greedy $(1 + ε)$ -spanner…

math.CO2025

Erdős-Szekeres Maker-Breaker Games

Aleksa Džuklevski, Dömötör Pálvölgyi, Alexey Pokrovskiy +3

We present new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be…

cs.CG2025

Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6

Let $S$ be a set of $n$ points in $R^{d}$ , where $d \geq 2$ is a constant, and let $H_{1}, H_{2}, \dots, H_{m + 1}$ be a sequence of vertical hyperplanes that are sorted by their fi…