2 citations · 3 across the 8 of their papers we have counts for
10 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…
Nearest-Neighbor Decompositions of Drawings
Jonas Cleve, Nicolas Grelier, Kristin Knorr +3
Let be a set of straight-line segments in the plane, potentially crossing, and let be a positive integer. We denote by the union of the endpoints of the strai…
Compatible Spanning Trees in Simple Drawings of
Oswin Aichholzer, Kristin Knorr, Wolfgang Mulzer +6
For a simple drawing of the complete graph , two (plane) subdrawings are compatible if their union is plane. Let be the set of all plane spanning trees on…
Flipping Plane Spanning Paths
Oswin Aichholzer, Kristin Knorr, Wolfgang Mulzer +3
Let be a planar point set in general position, and let be the set of all plane straight-line paths with vertex set . A flip on a path …
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…
Dynamic Connectivity in Disk Graphs
Alexander Baumann, Haim Kaplan, Katharina Klost +4
Let be a set of sites in the plane, so that every site has an associated radius . Let be the disk intersection graph defined by , i.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…