Csaba D. Tóth

research

∙ 08/04/2023

On RAC Drawings of Graphs with Two Bends per Edge

It is shown that every n-vertex graph that admits a 2-bend RAC drawing i...

0 Csaba D. Tóth, et al. ∙

research

∙ 08/02/2023

Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time

A fundamental question in computational geometry is for a dynamic collec...

0 Sujoy Bhore, et al. ∙

research

∙ 07/03/2023

Reconfiguration of Polygonal Subdivisions via Recombination

Motivated by the problem of redistricting, we study area-preserving reco...

0 Hugo A. Akitaya, et al. ∙

research

∙ 06/20/2023

Observation Routes and External Watchman Routes

We introduce the Observation Route Problem () defined as follows: Given ...

0 Adrian Dumitrescu, et al. ∙

research

∙ 04/07/2023

Maximal Distortion of Geodesic Diameters in Polygonal Domains

For a polygon P with holes in the plane, we denote by ϱ(P) the ratio bet...

0 Adrian Dumitrescu, et al. ∙

research

∙ 08/20/2022

Minimizing Visible Edges in Polyhedra

We prove that, given a polyhedron 𝒫 in ℝ^3, every point in ℝ^3 that does...

0 Csaba D. Tóth, et al. ∙

research

∙ 06/29/2022

Minimum Weight Euclidean (1+ε)-Spanners

Given a set S of n points in the plane and a parameter ε>0, a Euclidean ...

0 Csaba D. Tóth, et al. ∙

research

∙ 06/20/2022

Euclidean Steiner Spanners: Light and Sparse

Lightness and sparsity are two natural parameters for Euclidean (1+ε)-sp...

0 Sujoy Bhore, et al. ∙

research

∙ 05/06/2022

Finding Points in Convex Position in Density-Restricted Sets

For a finite set A⊂ℝ^d, let Δ(A) denote the spread of A, which is the ra...

0 Adrian Dumitrescu, et al. ∙

research

∙ 02/21/2022

Online Spanners in Metric Spaces

Given a metric space ℳ=(X,δ), a weighted graph G over X is a metric t-sp...

0 Sujoy Bhore, et al. ∙

research

∙ 12/14/2021

Hop-Spanners for Geometric Intersection Graphs

A t-spanner of a graph G=(V,E) is a subgraph H=(V,E') that contains a uv...

0 Jonathan B. Conroy, et al. ∙

research

∙ 12/06/2021

Aspect Ratio Universal Rectangular Layouts

A generic rectangular layout (for short, layout) is a subdivision of an ...

0 Stefan Felsner, et al. ∙

research

∙ 07/01/2021

Online Euclidean Spanners

In this paper, we study the online Euclidean spanners problem for points...

0 Sujoy Bhore, et al. ∙

research

∙ 12/03/2020

Light Euclidean Steiner Spanners in the Plane

Lightness is a fundamental parameter for Euclidean spanners; it is the r...

0 Sujoy Bhore, et al. ∙

research

∙ 11/14/2020

Reconfiguration of Connected Graph Partitions via Recombination

Motivated by applications in gerrymandering detection, we study a reconf...

0 Hugo A. Akitaya, et al. ∙

research

∙ 10/06/2020

On Euclidean Steiner (1+ε)-Spanners

Lightness and sparsity are two natural parameters for Euclidean (1+ε)-sp...

0 Sujoy Bhore, et al. ∙

research

∙ 08/25/2020

Simple Topological Drawings of k-Planar Graphs

Every finite graph admits a simple (topological) drawing, that is, a dra...

0 Michael Hoffmann, et al. ∙

research

∙ 08/24/2020

Polygons with Prescribed Angles in 2D and 3D

We consider the construction of a polygon P with n vertices whose turnin...

0 Alon Efrat, et al. ∙

research

∙ 07/20/2020

Rainbow polygons for colored point sets in the plane

Given a colored point set in the plane, a perfect rainbow polygon is a s...

0 David Flores-Peñaloza, et al. ∙

research

∙ 06/26/2020

Cutting Polygons into Small Pieces with Chords: Laser-Based Localization

Motivated by indoor localization by tripwire lasers, we study the proble...

0 Esther M. Arkin, et al. ∙

research

∙ 06/19/2020

Universal Geometric Graphs

We introduce and study the problem of constructing geometric graphs that...

0 Fabrizio Frati, et al. ∙

research

∙ 04/16/2020

Compatible Paths on Labelled Point Sets

Let P and Q be finite point sets of the same cardinality in ℝ^2, each la...

0 Elena Arseneva, et al. ∙

research

∙ 02/18/2020

Sparse Hop Spanners for Unit Disk Graphs

A unit disk graph G on a given set of points P in the plane is a geometr...

0 Adrian Dumitrescu, et al. ∙

research

∙ 09/16/2019

Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

This is the arXiv index for the electronic proceedings of GD 2019, which...

0 Daniel Archambault, et al. ∙

research

∙ 08/31/2019

Simple k-Planar Graphs are Simple (k+1)-Quasiplanar

A simple topological graph is k-quasiplanar (k≥ 2) if it contains no k p...

0 Patrizio Angelini, et al. ∙

research

∙ 07/30/2019

Atomic Embeddability, Clustered Planarity, and Thickenability

We study the atomic embeddability testing problem, which is a common gen...

0 Radoslav Fulek, et al. ∙

research

∙ 06/24/2019

On the Stretch Factor of Polygonal Chains

Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P...

0 Ke Chen, et al. ∙

research

∙ 06/19/2019

Rock Climber Distance: Frogs versus Dogs

The classical measure of similarity between two polygonal chains in Eucl...

0 Hugo A. Akitaya, et al. ∙

research

∙ 03/17/2019

Circumscribing Polygons and Polygonizations for Disjoint Line Segments

Given a planar straight-line graph G=(V,E) in R^2, a circumscribing poly...

0 Hugo A. Akitaya, et al. ∙

research

∙ 02/27/2019

Reconfiguration of Connected Graph Partitions

Motivated by recent computational models for redistricting and detection...

0 Hugo A. Akitaya, et al. ∙

research

∙ 09/19/2018

Improved Bounds on Information Dissemination by Manhattan Random Waypoint Model

With the popularity of portable wireless devices it is important to mode...

0 Aria Rezaei, et al. ∙

research

∙ 08/23/2018

Crossing Minimization in Perturbed Drawings

Due to data compression or low resolution, nearby vertices and edges of ...

0 Radoslav Fulek, et al. ∙

research

∙ 06/25/2018

Maximum Area Axis-Aligned Square Packings

Given a point set S={s_1,... , s_n} in the unit square U=[0,1]^2, an anc...

0 Hugo A. Akitaya, et al. ∙

research

∙ 09/26/2017

Recognizing Weak Embeddings of Graphs

We present an efficient algorithm for a problem in the interface between...

0 Hugo A. Akitaya, et al. ∙

research

∙ 08/25/2017

Gap-planar Graphs

We introduce the family of k-gap-planar graphs for k ≥ 0, i.e., graphs t...

0 Sang Won Bae, et al. ∙

research

∙ 08/08/2017

Online unit clustering in higher dimensions

We revisit the online Unit Clustering problem in higher dimensions: Give...

0 Adrian Dumitrescu, et al. ∙

Csaba D. Tóth

Featured Co-authors