9 papers
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…
Edge densities of drawings of graphs with one forbidden cell
Benedikt Hahn, Torsten Ueckerdt, Birgit Vogtenhuber
A connected topological drawing of a graph divides the plane into a number of cells. The type of a cell is the cyclic sequence of crossings and vertices along the boundary walk…
Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
Oswin Aichholzer, Joseph Dorfer, Peter Kramer +2
We study the reconfiguration of plane spanning trees on point sets in the plane in convex position, where a reconfiguration step (flip) replaces one edge with another, yielding aga…
Monotonically Decreasing the Number of Directed 3-Cycles via Edge-Flips?
David Bom, Florian Unger, Birgit Vogtenhuber
We investigate a combinatorial reconfiguration problem on oriented graphs, where a reconfiguration step (edge-flip) is the inversion of the orientation of a single edge. A recently…
Crossing and non-crossing families
Todor AntiÄ, Martin Balko, Birgit Vogtenhuber
For a finite set of points in the plane in general position, a \emph{crossing family} of size in is a collection of line segments with endpoints in that are pai…
Characterizing and Recognizing Twistedness
Oswin Aichholzer, Alfredo GarcÃa, Javier Tejel +2
In a simple drawing of a graph, any two edges intersect in at most one point (either a common endpoint or a proper crossing). A simple drawing is generalized twisted if it fulfills…