research
∙
09/29/2022
Minimum Link Fencing
We study a variant of the geometric multicut problem, where we are given...
share
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
∙
01/19/2021
Local Complexity of Polygons
Many problems in Discrete and Computational Geometry deal with simple po...
research
∙
12/21/2020
Efficient Segment Folding is Hard
We introduce a computational origami problem which we call the segment f...
research
∙
12/14/2020
Crossing-Optimal Extension of Simple Drawings
In extension problems of partial graph drawings one is given an incomple...
research
∙
12/03/2020
Saturated k-Plane Drawings with Few Edges
A drawing of a graph is k-plane if no edge is crossed more than k times....
research
∙
07/08/2020
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
The problem of extending partial geometric graph representations such as...
research
∙
04/25/2020
Extending Partial 1-Planar Drawings
Algorithmic extension problems of partial graph representations such as ...
research
∙
04/16/2020
Four Pages Are Indeed Necessary for Planar Graphs
An embedding of a graph in a book consists of a linear order of its vert...
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/26/2020
Finding large matchings in 1-planar graphs of minimum degree 3
A matching is a set of edges without common endpoint. It was recently sh...
research
∙
10/17/2019
Exploring Semi-Automatic Map Labeling
Label placement in maps is a very challenging task that is critical for ...
research
∙
09/16/2019
Extending simple drawings with one edge is hard
A simple drawing D(G) of a graph G = (V,E) is a drawing in which two edg...
research
∙
08/23/2019
Mixed Linear Layouts: Complexity, Heuristics, and Experiments
A k-page linear graph layout of a graph G = (V,E) draws all vertices alo...
research
∙
08/23/2019
Maximizing Ink in Partial Edge Drawings of k-plane Graphs
Partial edge drawing (PED) is a drawing style for non-planar graphs, in ...
research
∙
08/14/2019
On Strict (Outer-)Confluent Graphs
A strict confluent (SC) graph drawing is a drawing of a graph with verti...
research
∙
03/15/2018
