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...
share
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...
research
∙
07/03/2023
Reconfiguration of Polygonal Subdivisions via Recombination
Motivated by the problem of redistricting, we study area-preserving reco...
research
∙
06/20/2023
Observation Routes and External Watchman Routes
We introduce the Observation Route Problem () defined as follows: Given ...
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...
research
∙
08/20/2022
Minimizing Visible Edges in Polyhedra
We prove that, given a polyhedron 𝒫 in ℝ^3, every point in ℝ^3 that does...
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 ...
research
∙
06/20/2022
Euclidean Steiner Spanners: Light and Sparse
Lightness and sparsity are two natural parameters for Euclidean (1+ε)-sp...
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...
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...
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...
research
∙
12/06/2021
Aspect Ratio Universal Rectangular Layouts
A generic rectangular layout (for short, layout) is a subdivision of an ...
research
∙
07/01/2021
Online Euclidean Spanners
In this paper, we study the online Euclidean spanners problem for points...
research
∙
12/03/2020
Light Euclidean Steiner Spanners in the Plane
Lightness is a fundamental parameter for Euclidean spanners; it is the r...
research
∙
11/14/2020
Reconfiguration of Connected Graph Partitions via Recombination
Motivated by applications in gerrymandering detection, we study a reconf...
research
∙
10/06/2020
On Euclidean Steiner (1+ε)-Spanners
Lightness and sparsity are two natural parameters for Euclidean (1+ε)-sp...
research
∙
08/25/2020
Simple Topological Drawings of k-Planar Graphs
Every finite graph admits a simple (topological) drawing, that is, a dra...
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...
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...
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...
research
∙
06/19/2020
Universal Geometric Graphs
We introduce and study the problem of constructing geometric graphs that...
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...
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...
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...
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...
research
∙
07/30/2019
Atomic Embeddability, Clustered Planarity, and Thickenability
We study the atomic embeddability testing problem, which is a common gen...
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...
research
∙
06/19/2019
Rock Climber Distance: Frogs versus Dogs
The classical measure of similarity between two polygonal chains in Eucl...
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...
research
∙
02/27/2019
Reconfiguration of Connected Graph Partitions
Motivated by recent computational models for redistricting and detection...
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...
research
∙
08/23/2018
Crossing Minimization in Perturbed Drawings
Due to data compression or low resolution, nearby vertices and edges of ...
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...
research
∙
09/26/2017
Recognizing Weak Embeddings of Graphs
We present an efficient algorithm for a problem in the interface between...
research
∙
08/25/2017
Gap-planar Graphs
We introduce the family of k-gap-planar graphs for k ≥ 0, i.e., graphs t...
research
∙
08/08/2017