73 citations · 178 across the 49 of their papers we have counts for
14 papers · 1 filter
Rerouting Curves on Surfaces
Timo Brand, Stefan Felsner, Henry Förster +8
We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on…
Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds
Håvard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist +2
We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set of points in general position in the plane, the flip graph has a vertex…
On the complexity of embedding in graph products
Therese Biedl, David Eppstein, Torsten Ueckerdt
Graph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of…
Edge-Minimum Saturated k-Planar Drawings
Steven Chaplick, Fabian Klute, Irene Parada +2
For a class of drawings of loopless (multi-)graphs in the plane, a drawing is \emph{saturated} when the addition of any edge to results in $D'…
On the Maximum Crossing Number
Markus Chimani, Stefan Felsner, Stephen Kobourov +3
Research about crossings is typically about minimization. In this paper, we consider \emph{maximizing} the number of crossings over all possible ways to draw a given graph in the p…
Convex-Arc Drawings of Pseudolines
David Eppstein, Mereke van Garderen, Bettina Speckmann +1
A weak pseudoline arrangement is a topological generalization of a line arrangement, consisting of curves topologically equivalent to lines that cross each other at most once. We c…