1 citations · 1 across the 10 of their papers we have counts for
11 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…
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…
Constrained Flips in Plane Spanning Trees
Oswin Aichholzer, Joseph Dorfer, Birgit Vogtenhuber
A flip in a plane spanning tree is the operation of removing one edge from and adding another edge such that the resulting structure is again a plane spanning tree. For tre…
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…
On the geometric -colored crossing number of
Benedikt Hahn, Bettina Klinz, Birgit Vogtenhuber
We study the \emph{geometric -colored crossing number} of complete graphs , which is the smallest number of monochromatic crossings in an…
Flipping Non-Crossing Spanning Trees
Håvard Bakke Bjerkevik, Linda Kleist, Torsten Ueckerdt +1
For a set of points in general position in the plane, the flip graph has a vertex for each non-crossing spanning tree on and an edge between any two spanning tre…
Geometric Thickness of Multigraphs is -complete
Henry Förster, Philipp Kindermann, Tillmann Miltzow +3
We say that a (multi)graph has geometric thickness if there exists a straight-line drawing and a -coloring of its edges where no…
Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles
Yan Alves Radtke, Stefan Felsner, Johannes Obenaus +3
Flip graphs of combinatorial and geometric objects are at the heart of many deep structural insights and connections between different branches of discrete mathematics and computer…