3 papers
cs.CG2026
Parameterized Approximation of Rectangle Stabbing
Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4
In the Rectangle Stabbing problem, input is a set of axis-parallel rectangles and a set of axis parallel lines in the plane. The task is to find a minimum siz…
cs.CG2025
Approximation and Hardness of Polychromatic TSP
Thomas Schibler, Subhash Suri, Jie Xue
We introduce the Polychromatic Traveling Salesman Problem (PCTSP), where the input is an edge weighted graph whose vertices are partitioned into equal-sized color classes, and…
cs.CG2025
Embedding Graphs as Euclidean kNN-Graphs
T. Schibler, S. Suri, J. Xue
Let G = (V, E) be a directed graph on n vertices where each vertex has out-degree k. We say that G is kNN-realizable in d-dimensional Euclidean space if there exists a point set P…