10 papers
Component Order Connectivity in Directed Graphs
J. Bang-Jensen, E. Eiben, G. Gutin +2
A directed graph is semicomplete if for every pair of vertices of there is at least one arc between and \viol{Thus, a tournament is a semicomplete digraph.}…
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
Eduard Eiben, Robert Ganian, Thekla Hamm +2
The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph , a conne…
A Polynomial Kernel for Line Graph Deletion
Eduard Eiben, William Lochet
The line graph of a graph is the graph whose vertex set is the edge set of and there is an edge between if and share an endpoint in . A grap…
Extending Partial 1-Planar Drawings
Eduard Eiben, Robert Ganian, Thekla Hamm +2
Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph…
Manipulating Districts to Win Elections: Fine-Grained Complexity
Eduard Eiben, Fedor V. Fomin, Fahad Panolan +1
Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AA…
Removing Connected Obstacles in the Plane is FPT
Eduard Eiben, Daniel Lokshtanov
Given two points in the plane, a set of obstacles defined by closed curves, and an integer , does there exist a path between the two designated points intersecting at most o…