research
∙
06/14/2023
On the Restricted k-Steiner Tree Problem
Given a set P of n points in ℝ^2 and an input line γ in ℝ^2, we present ...
share
research
∙
05/30/2022
Linear versus centred chromatic numbers
We prove that the linear chromatic number of any k× k pseudogrid is Ω(k)...
research
∙
04/25/2022
Pursuit-Evasion in Graphs: Zombies, Lazy Zombies and a Survivor
We study zombies and survivor, a variant of the game of cops and robber ...
research
∙
02/17/2022
An Optimal Algorithm for Product Structure in Planar Graphs
The Product Structure Theorem for planar graphs (Dujmović et al.JACM, 67...
research
∙
11/27/2021
On approximating shortest paths in weighted triangular tessellations
We study the quality of weighted shortest paths when a continuous 2-dime...
research
∙
06/28/2021
Dynamic Schnyder Woods
A realizer, commonly known as Schnyder woods, of a triangulation is a pa...
research
∙
06/02/2021
Improved Spanning on Theta-5
We show an upper bound of sin(3π/10) /sin(2π/5)-sin(3π/10) <5.70 ...
research
∙
05/04/2021
Separating layered treewidth and row treewidth
Layered treewidth and row treewidth are recently introduced graph parame...
research
∙
01/30/2021
Fragile Complexity of Adaptive Algorithms
The fragile complexity of a comparison-based algorithm is f(n) if each i...
research
∙
11/04/2020
Affine invariant triangulations
We study affine invariant 2D triangulation methods. That is, methods tha...
research
∙
07/13/2020
Asymptotically Optimal Vertex Ranking of Planar Graphs
A (vertex) ℓ-ranking is a labelling φ:V(G)→ℕ of the vertices of a graph ...
research
∙
02/22/2020
(Faster) Multi-Sided Boundary Labelling
A 1-bend boundary labelling problem consists of an axis-aligned rectangl...
research
∙
02/13/2020
Drawing Graphs as Spanners
We study the problem of embedding graphs in the plane as good geometric ...
research
∙
02/12/2020
Parameterized Complexity of Two-Interval Pattern Problem
A 2-interval is the union of two disjoint intervals on the real line. Tw...
research
∙
10/31/2019
Expected Complexity of Routing in Θ 6 and Half-Θ 6 Graphs
We study online routing algorithms on the Θ6-graph and the half-Θ6-graph...
research
∙
08/02/2019
Competitive Online Search Trees on Trees
We consider the design of adaptive data structures for searching element...
research
∙
03/17/2019
Computing Maximum Independent Set on Outerstring Graphs and Their Relatives
A graph G with n vertices is called an outerstring graph if it has an in...
research
∙
12/24/2018
Near-Optimal O(k)-Robust Geometric Spanners
For any constants d> 1, ϵ >0, t>1, and any n-point set P⊂R^d, we show th...
research
∙
12/17/2018
Stabbing Pairwise Intersecting Disks by Four Points
Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...
research
∙
09/26/2018
Gathering by Repulsion
We consider a repulsion actuator located in an n-sided convex environmen...
research
∙
08/31/2018
Pole Dancing: 3D Morphs for Tree Drawings
We study the question whether a crossing-free 3D morph between two strai...
research
∙
08/03/2018
On the Spanning and Routing Ratio of Theta-Four
We present a routing algorithm for the Theta-4-graph that computes a pat...
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/28/2018
Boundary Labeling for Rectangular Diagrams
Given a set of n points (sites) inside a rectangle R and n points (label...
research
∙
03/09/2018
Geodesic Obstacle Representation of Graphs
An obstacle representation of a graph is a mapping of the vertices onto ...
research
∙
03/08/2018
Routing on the Visibility Graph
We consider the problem of routing on a network in the presence of line ...
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/07/2018
Reconstructing a convex polygon from its ω-cloud
An ω-wedge is the (closed) set of all points contained between two rays ...
research
∙
10/23/2017
Constrained Routing Between Non-Visible Vertices
In this paper we study local routing strategies on geometric graphs. Suc...
research
∙
08/14/2017
On the Separation of a Polyhedron from Its Single-Part Mold
Casting is a manufacturing process where liquid material is poured into ...
research
∙
06/25/2017
Optimal Art Gallery Localization is NP-hard
Art Gallery Localization (AGL) is the problem of placing a set T of broa...
research
∙
06/21/2017
Art Gallery Localization
We study the problem of placing a set T of broadcast towers in a simple ...
research
∙
07/09/2015
The Shadows of a Cycle Cannot All Be Paths
A "shadow" of a subset S of Euclidean space is an orthogonal projection ...
research
∙
05/01/2008