6 papers
Metric Planarity Testing is Hard
Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak +3
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for…
Dynamic data structures for twin-ordered matrices
Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…
Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
Sujoy Bhore, Sándor Kisfaludi-Bak, Lazar Milenković +3
A Euclidean noncrossing Steiner -spanner for a point set is a planar straight-line graph that, for any two points , contains a path whose…
Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are given a weighted set of axis-parallel rectangles in the plane. The task is to find a subset of pairwi…
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
François Dross, Krzysztof Fleszar, Karol Węgrzycki +1
In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that con…
Dynamic data structures for parameterized string problems
Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki +2
We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a…