5 papers
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…
Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods
Samuel Schneider, Torsten Ueckerdt
Chernyshev, Rauch and Rautenbach [Discrete Math., 2025] introduce forest cuts, i.e., vertex separators that induce a forest. They conjecture that, similar to a result by Chen and Y…
Linear Layouts of Graphs with Priority Queues
Emilio Di Giacomo, Walter Didimo, Henry Förster +2
A linear layout of a graph consists of a linear ordering of its vertices and a partition of its edges into pages such that the edges assigned to the same page obey some constraint.…
Crossing Number of 3-Plane Drawings
Miriam Goetze, Michael Hoffmann, Ignaz Rutter +1
We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings…
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…