research
∙
03/08/2023
Improved Bounds for Covering Paths and Trees in the Plane
A covering path for a planar point set is a path drawn in the plane with...
share
research
∙
11/30/2021
Acute Tours in the Plane
We confirm the following conjecture of Fekete and Woeginger from 1997: f...
research
∙
11/10/2021
Approximating bottleneck spanning trees on partitioned tuples of points
We present approximation algorithms for the following NP-hard optimizati...
research
∙
10/08/2020
Improved approximation ratios for two Euclidean maximum spanning tree problems
We study the following two maximization problems related to spanning tre...
research
∙
08/12/2020
A short proof of the non-biplanarity of K_9
Battle, Harary, and Kodama (1962) and independently Tutte (1963) proved ...
research
∙
06/22/2020
Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs
Given a connected vertex-weighted graph G, the maximum weight internal s...
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
∙
11/19/2019
Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Inspired by the seminal works of Khuller et al. (STOC 1994) and Chan (So...
research
∙
07/02/2019
A Short Proof of the Toughness of Delaunay Triangulations
We present a self-contained short proof of the seminal result of Dillenc...
research
∙
06/27/2019
Packing Boundary-Anchored Rectangles and Squares
Consider a set P of n points on the boundary of an axis-aligned square Q...
research
∙
05/02/2019
Flip Distance to some Plane Configurations
We study an old geometric optimization problem in the plane. Given a per...
research
∙
05/02/2019
Minimum Ply Covering of Points with Disks and Squares
Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we ...
research
∙
03/16/2019
Token Swapping on Trees
The input to the token swapping problem is a graph with vertices v_1, v_...
research
∙
02/26/2019
Plane Hop Spanners for Unit Disk Graphs: Simpler and Better
The unit disk graph (UDG) is a widely employed model for the study of wi...
research
∙
01/06/2019
Maximum Matchings and Minimum Blocking Sets in Θ_6-Graphs
Θ_6-Graphs are important geometric graphs that have many applications es...
research
∙
12/17/2018
Stabbing Pairwise Intersecting Disks by Four Points
Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...
research
∙
10/22/2018
On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart (196...
research
∙
09/27/2018
Plane and Planarity Thresholds for Random Geometric Graphs
A random geometric graph, G(n,r), is formed by choosing n points indepen...
research
∙
04/19/2018
Improved Bounds for Guarding Plane Graphs with Edges
An "edge guard set" of a plane graph G is a subset Γ of edges of G such ...
research
∙
03/06/2018
Packing Plane Spanning Trees into a Point Set
Let P be a set of n points in the plane in general position. We show tha...
research
∙
02/26/2018
Faster Algorithms for some Optimization Problems on Collinear Points
We propose faster algorithms for the following three optimization proble...
research
∙
01/25/2018
Rollercoasters and Caterpillars
A rollercoaster is a sequence of real numbers for which every maximal co...
research
∙
06/25/2017