5 papers
On RAC Drawings of Graphs with Two Bends per Edge
Csaba D. Tóth
It is shown that every -vertex graph that admits a 2-bend RAC drawing in the plane, where the edges are polylines with two bends per edge and any pair of edges can only cross at…
Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time
Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth +1
A fundamental question is whether one can maintain a maximum independent set in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. Alread…
Reconfiguration of Polygonal Subdivisions via Recombination
Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine +2
Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon $\mathcal{R…
Observation Routes and External Watchman Routes
Adrian Dumitrescu, Csaba D. Tóth
We introduce the Observation Route Problem () defined as follows: Given a set of pairwise disjoint compact regions in the plane, find a shortest tour (route) such…
Maximal Distortion of Geodesic Diameters in Polygonal Domains
Adrian Dumitrescu, Csaba D. Tóth
For a polygon with holes in the plane, we denote by the ratio between the geodesic and the Euclidean diameters of . It is shown that over all convex polygons wi…