1 citations · 1 across the 2 of their papers we have counts for
4 papers
The density of iterated crossing points and a gap result for triangulations of finite point sets
Rolf Klein, Martin Kutz
Consider a plane graph G, drawn with straight lines. For every pair a,b of vertices of G, we compare the shortest-path distance between a and b in G (with Euclidean edge lengths) t…
Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time
Martin Kutz
We present an algorithm that computes a shortest non-contractible and a shortest non-separating cycle on an orientable combinatorial surface of bounded genus in O(n \log n) time, w…
A pair of trees without a simultaneous geometric embedding in the plane
Martin Kutz
Any planar graph has a crossing-free straight-line drawing in the plane. A simultaneous geometric embedding of two n-vertex graphs is a straight-line drawing of both graphs on a co…
Computing roots of directed graphs is graph isomorphism hard
Martin Kutz
The k-th power D^k of a directed graph D is defined to be the directed graph on the vertices of D with an arc from a to b in D^k iff one can get from a to b in D with exactly k ste…