11 citations · 35 across the 50 of their papers we have counts for
8 papers · 1 filter
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
Jie Gao, Pawel Gawrychowski, Panos Giannopoulos +4
A \emph{disk graph} is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs,…
Parameterized Geometric Graph Modification with Disk Scaling
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph and an integer $k\in\mathb…
Kernelization for Spreading Points
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance,…
(Re)packing Equal Disks into Rectangle
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without ov…
A Framework for Approximation Schemes on Disk Graphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
We initiate a systematic study of approximation schemes for fundamental optimization problems on disk graphs, a common generalization of both planar graphs and unit-disk graphs. Ou…
Parameterized Approaches to Orthogonal Compaction
Walter Didimo, Siddharth Gupta, Philipp Kindermann +3
Orthogonal graph drawings are used in applications such as UML diagrams, VLSI layout, cable plans, and metro maps. We focus on drawing planar graphs and assume that we are given an…
Parameterized Study of Steiner Tree on Unit Disk Graphs
Sujoy Bhore, Paz Carmi, Sudeshna Kolay +1
We study the Steiner Tree problem on unit disk graphs. Given a vertex unit disk graph , a subset of vertices and a positive integer , the objective…
The Parameterized Complexity of Guarding Almost Convex Polygons
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov +2
Art Gallery is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an int…