research
∙
08/30/2023
On Colorful Vertex and Edge Cover Problems
In this paper, we study two generalizations of Vertex Cover and Edge Cov...
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
∙
02/21/2023
Dynamic Euclidean Bottleneck Matching
A fundamental question in computational geometry is for a set of input p...
research
∙
02/20/2023
Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
The task of finding an extension to a given partial drawing of a graph w...
research
∙
09/29/2022
Minimum Link Fencing
We study a variant of the geometric multicut problem, where we are given...
research
∙
07/03/2022
On Streaming Algorithms for Geometric Independent Set and Clique
We study the maximum geometric independent set and clique problems in th...
research
∙
06/20/2022
Euclidean Steiner Spanners: Light and Sparse
Lightness and sparsity are two natural parameters for Euclidean (1+ε)-sp...
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
∙
11/18/2021
Untangling Circular Drawings: Algorithms and Complexity
We consider the problem of untangling a given (non-planar) straight-line...
research
∙
09/09/2021
Worbel: Aggregating Point Labels into Word Clouds
Point feature labeling is a classical problem in cartography and GIS tha...
research
∙
08/27/2021
On the Upward Book Thickness Problem: Combinatorial and Complexity Results
A long-standing conjecture by Heath, Pemmaraju, and Trenk states that th...
research
∙
07/01/2021
Online Euclidean Spanners
In this paper, we study the online Euclidean spanners problem for points...
research
∙
06/28/2021
Dynamic Schnyder Woods
A realizer, commonly known as Schnyder woods, of a triangulation is a pa...
research
∙
03/15/2021
Unit Disk Representations of Embedded Trees, Outerplanar and Multi-Legged Graphs
A unit disk intersection representation (UDR) of a graph G represents ea...
research
∙
01/13/2021
Space-Efficient Algorithms for Reachability in Geometric Graphs
The problem of graph Reachability is to decide whether there is a path f...
research
∙
12/03/2020
Light Euclidean Steiner Spanners in the Plane
Lightness is a fundamental parameter for Euclidean spanners; it is the r...
research
∙
10/06/2020
On Euclidean Steiner (1+ε)-Spanners
Lightness and sparsity are two natural parameters for Euclidean (1+ε)-sp...
research
∙
08/19/2020
Parameterized Algorithms for Queue Layouts
An h-queue layout of a graph G consists of a linear order of its vertice...
research
∙
07/16/2020
Dynamic Geometric Independent Set
We present fully dynamic approximation algorithms for the Maximum Indepe...
research
∙
04/20/2020
Parameterized Study of Steiner Tree on Unit Disk Graphs
We study the Steiner Tree problem on unit disk graphs. Given a n vertex ...
research
∙
04/19/2020
Planar Bichromatic Bottleneck Spanning Trees
Given a set P of n red and blue points in the plane, a planar bichromati...
research
∙
03/11/2020
Balanced Independent and Dominating Sets on Colored Interval Graphs
We study two new versions of independent and dominating set problems on ...
research
∙
02/18/2020
Independent Sets of Dynamic Rectangles: Algorithms and Experiments
We study the maximal independent set (MIS) and maximum independent set (...
research
∙
02/13/2020
Geometric Systems of Unbiased Representatives
Let P be a set of points in ℝ^d, B a bicoloring of P and a family of ge...
research
∙
11/20/2019
Geometric Planar Networks on Bichromatic Points
We study four classical graph problems – Hamiltonian path, Traveling sal...
research
∙
09/09/2019
Balanced Connected Subgraph Problem in Geometric Intersection Graphs
We study the Balanced Connected Subgraph(shortly, BCS) problem on geomet...
research
∙
08/23/2019
Parameterized Algorithms for Book Embedding Problems
A k-page book embedding of a graph G draws the vertices of G on a line a...
research
∙
02/27/2019
Algorithm and Hardness results on Liar's Dominating Set and k-tuple Dominating Set
Given a graph G=(V,E), the dominating set problem asks for a minimum sub...
research
∙
09/24/2018