6 papers
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
Jesse Beisegel, Katharina Klost, Kristin Knorr +2
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width…
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
Jesse Beisegel, Katharina Klost, Kristin Knorr +2
We consider the problem of finding a Hamiltonian path or a Hamiltonian cycle with precedence constraints in the form of a partial order on the vertex set. We show that the path pro…
A Graph Width Perspective on Partially Ordered Hamiltonian Paths
Jesse Beisegel, Katharina Klost, Kristin Knorr +2
We consider the problem of finding a Hamiltonian path with precedence constraints in the form of a partial order on the vertex set. This problem is known as Partially Ordered Hamil…
Insertion-Only Dynamic Connectivity in General Disk Graphs
Haim Kaplan, Katharina Klost, Kristin Knorr +2
Let be a set of \emph{sites} in the plane, so that every site has an \emph{associated radius} . Let be the \emph{disk inter…
Simplifying Non-Simple Fan-Planar Drawings
Boris Klemz, Kristin Knorr, Meghana M. Reddy +1
A drawing of a graph is fan-planar if the edges intersecting a common edge share a vertex on the same side of . More precisely, orienting arbitrarily and the other e…
On the Maximum Number of Crossings in Star-Simple Drawings of with No Empty Lens
Stefan Felsner, Michael Hoffmann, Kristin Knorr +1
A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. W…