3 citations · 5 across the 11 of their papers we have counts for
18 papers · 1 filter
Bowties and Hourglasses: Intersections of Double-Wedges (or Stabbing and Avoiding Line Segments)
Daniel Bertschinger, Henry Förster, Fabian Klute +3
We study the common intersection of arrangements of double-wedges. We consider arrangements where double-wedges may be either bowties (which do not contain a vertical line) or hour…
Algorithms for Distance Problems in Continuous Graphs
Sergio Cabello, Delia Garijo, Antonia Kalb +3
We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices,…
Computing crossing numbers with topological and geometric restrictions
Thekla Hamm, Fabian Klute, Irene Parada
Computing the crossing number of a graph is one of the most classical problems in computational geometry. Both it and numerous variations of the problem have been studied, and over…
Barking dogs: A Fréchet distance variant for detour detection
Ivor van der Hoog, Fabian Klute, Irene Parada +1
Imagine you are a dog behind a fence and a hiker is passing by at constant speed along the hiking path . In order to fulfil your duties as a watchdog, you desire to bark as…
On -Plane Insertion into Plane Drawings
Julia Katheder, Philipp Kindermann, Fabian Klute +2
We introduce the -Plane Insertion into Plane drawing (-PIP) problem: given a plane drawing of a planar graph and a set of edges, insert the edges in into the draw…
Minimum Link Fencing
Sujoy Bhore, Fabian Klute, Maarten Löffler +3
We study a variant of the geometric multicut problem, where we are given a set of colored and pairwise interior-disjoint polygons in the plane. The objective is to co…
On Streaming Algorithms for Geometric Independent Set and Clique
Sujoy Bhore, Fabian Klute, Jelle J. Oostveen
We study the maximum geometric independent set and clique problems in the streaming model. Given a collection of geometric objects arriving in an insertion only stream, the aim is…
Local Complexity of Polygons
Fabian Klute, Meghana M. Reddy, Tillmann Miltzow
Many problems in Discrete and Computational Geometry deal with simple polygons or polygonal regions. Many algorithms and data-structures perform considerably faster, if the underly…
Crossing-Optimal Extension of Simple Drawings
Robert Ganian, Thekla Hamm, Fabian Klute +2
In extension problems of partial graph drawings one is given an incomplete drawing of an input graph and is asked to complete the drawing while maintaining certain properties.…
Efficient Segment Folding is Hard
Takashi Horiyama, Fabian Klute, Matias Korman +3
We introduce a computational origami problem which we call the segment folding problem: given a set of line-segments in the plane the aim is to make creases along all segments…
Saturated -Plane Drawings with Few Edges
Fabian Klute, Irene Parada
A drawing of a graph is -plane if no edge is crossed more than times. In this paper we study saturated -plane drawings with few edges. This are -plane drawings in whic…
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
Eduard Eiben, Robert Ganian, Thekla Hamm +2
The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph , a conne…
Finding large matchings in 1-planar graphs of minimum degree 3
Therese Biedl, Fabian Klute
A matching is a set of edges without common endpoint. It was recently shown that every 1-planar graph (i.e., a graph that can be drawn in the plane with at most one crossing per ed…
Exploring Semi-Automatic Map Labeling
Fabian Klute, Guangping Li, Raphael Löffler +2
Label placement in maps is a very challenging task that is critical for the overall map quality. Most previous work focused on designing and implementing fully automatic solutions,…
Inserting one edge into a simple drawing is hard
Alan Arroyo, Fabian Klute, Irene Parada +3
A {\em simple drawing} of a graph is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge in the complement o…
Maximizing Ink in Partial Edge Drawings of k-plane Graphs
Matthias Hummel, Fabian Klute, Soeren Nickel +1
Partial edge drawing (PED) is a drawing style for non-planar graphs, in which edges are drawn only partially as pairs of opposing stubs on the respective end-vertices. In a PED, by…
On Strict (Outer-)Confluent Graphs
Henry Förster, Robert Ganian, Fabian Klute +1
A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by…
Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts
Fabian Klute, Martin Nöllenburg
Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is \NP-h…