4 papers
Edge-Constrained Hamiltonian Paths on a Point Set
Todor Antić, Aleksa Džuklevski, Jiří Fiala +5
Let S be a set of distinct points in general position in the Euclidean plane. A plane Hamiltonian path on S is a crossing-free geometric path such that every point of S is a vertex…
Hypergraphs as Metro Maps: Drawing Paths with Few Bends in Trees, Cacti, and Plane 4-Graphs
Sabine Cornelsen, Henry Förster, Siddharth Gupta +2
A hypergraph consists of a set of vertices and a set of subsets of vertices, called hyperedges. In the metro map metaphor, each hyperedge is represented by a path (the metro line)…
Drawing Trees and Cacti with Integer Edge Lengths on a Polynomial-Size Grid
Henry Förster, Stephen Kobourov, Jacob Miller +1
A strengthened version of Harborth's well-known conjecture -- known as Kleber's conjecture -- states that every planar graph admits a planar straight-line drawing where every edge…
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.…