1 citations · 1 across the 1 of their papers we have counts for
Showing cs.CGShow all
3 papers · 1 filter
cs.CG2006
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…
cs.CG2005
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…
cs.CG2005
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…