3 citations · 5 across the 11 of their papers we have counts for
24 papers
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…
Faces in rectilinear drawings of complete graphs
Martin Balko, Anna Brötzner, Fabian Klute +1
We initiate the study of extremal problems about faces in convex rectilinear drawings of~, that is, drawings where vertices are represented by points in the plane in convex po…
Strong odd coloring in minor-closed classes
Miriam Goetze, Fabian Klute, Kolja Knauer +3
We show that the strong odd chromatic number on any proper minor-closed graph class is bounded by a constant. We almost determine the smallest such constant for outerplanar graphs.
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…
Extending Partial 1-Planar Drawings
Eduard Eiben, Robert Ganian, Thekla Hamm +2
Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph…
Four Pages Are Indeed Necessary for Planar Graphs
Michael A. Bekos, Michael Kaufmann, Fabian Klute +3
An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two…
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…
Balanced Independent and Dominating Sets on Colored Interval Graphs
Sujoy Bhore, Jan-Henrik Haunert, Fabian Klute +2
We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely -Balanced Independent Set (-BIS) and -Balanced Dominating Se…
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…
Mixed Linear Layouts: Complexity, Heuristics, and Experiments
Philipp de Col, Fabian Klute, Martin Nöllenburg
A -page linear graph layout of a graph draws all vertices along a line and each edge in one of disjoint halfplanes called pages, which are bounded by $\el…
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…