Katharina Klost

activity

20172026

most citedDynamic Connectivity in Disk Graphs

2 citations · 2 across the 7 of their papers we have counts for

collaborators

13 papers

cs.CG2026

Geometric Give and Take

Oswin Aichholzer, Katharina Klost, Kristin Knorr +2

We consider a special, geometric case of a balancing game introduced by Spencer in 1977. Consider any arrangement $L$ of $n$ lines in the plane, and assume that each cell…

cs.CG2026

Compatible Triangulations of Simple Polygons

Peyman Afshani, Boris Aronov, Kevin Buchin +5

Let $P$ and $Q$ be simple polygons with $n$ vertices each. We wish to compute triangulations of $P$ and $Q$ that are combinatorially equivalent, if they exist. We consider two vers…

cs.DM2025

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…

cs.DM2025

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…

cs.DM2025

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…

cs.CG2025

Minimum spanning blob-trees

Katharina Klost, Marc van Kreveld, Daniel Perz +2

We investigate blob-trees, a new way of connecting a set of points, by a mixture of enclosing them by cycles (as in the convex hull) and connecting them by edges (as in a spanning…

cs.CG2024

Robust Algorithms for Finding Triangles and Computing the Girth in Unit Disk and Transmission Graphs

Katharina Klost, Wolfgang Mulzer

We describe optimal robust algorithms for finding a triangle and the unweighted girth in a unit disk graph, as well as finding a triangle in a transmission graph.In the robust sett…

cs.CG2023

Insertion-Only Dynamic Connectivity in General Disk Graphs

Haim Kaplan, Katharina Klost, Kristin Knorr +2

Let $S \subseteq R^{2}$ be a set of $n$ \emph{sites} in the plane, so that every site $s \in S$ has an \emph{associated radius} $r_{s} > 0$ . Let $D (S)$ be the \emph{disk inter…

cs.CG2021★ 2 cited

Dynamic Connectivity in Disk Graphs

Alexander Baumann, Haim Kaplan, Katharina Klost +4

Let $S$ be a set of $n$ sites in the plane, so that every site $s \in S$ has an associated radius $r_{s} > 0$ . Let $D (S)$ be the disk intersection graph defined by $S$ , i.e…

cs.CG2021

Long Plane Trees

Sergio Cabello, Michael Hoffmann, Katharina Klost +2

In the longest plane spanning tree problem, we are given a finite planar point set $P$ , and our task is to find a plane (i.e., noncrossing) spanning tree for $\mathcal{P}…

cs.CG2019

Triangles and Girth in Disk Graphs and Transmission Graphs

Haim Kaplan, Katharina Klost, Wolfgang Mulzer +3

Let $S \subset R^{2}$ be a set of $n$ sites, where each $s \in S$ has an associated radius $r_{s} > 0$ . The disk graph $D (S)$ is the undirected graph with vertex set $S$ and a…

cs.CG2019

Routing in Histograms

Man-Kwun Chiu, Jonas Cleve, Katharina Klost +5

Let $P$ be an $x$ -monotone orthogonal polygon with $n$ vertices. We call $P$ a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizonta…

cs.CG2017

Recognizing Generalized Transmission Graphs of Line Segments and Circular Sectors

Katharina Klost, Wolfgang Mulzer

Suppose we have an arrangement $A$ of $n$ geometric objects $x_{1}, \dots, x_{n} \subseteq R^{2}$ in the plane, with a distinguished point $p_{i}$ in each object $x_{i}$ .…