2 citations · 4 across the 12 of their papers we have counts for
17 papers
Point Set Embeddability with List Constraints
Thomas Depian, Joseph Dorfer, Boris Klemz +2
Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and…
On Compaction and Realizability of Almost Convex Octilinear Representations
Henry Förster, Giacomo Ortali, Lena Schlip
Octilinear graph drawings are a standard paradigm extending the orthogonal graph drawing style by two additional slopes (+1 and -1). We are interested in two constrained drawing pr…
Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
Mikkel Abrahamsen, Kevin Buchin, Maike Buchin +5
We study two well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the sta…
Minimum Monotone Spanning Trees
Emilio Di Giacomo, Walter Didimo, Eleni Katsanou +3
Given a finite set of points in the plane and a finite set of directions, a geometric spanning tree~ of~ is -monotone if every path in is m…
Weakly and Strongly Fan-Planar Graphs
Otfried Cheong, Henry Förster, Julia Katheder +2
We study two notions of fan-planarity introduced by (Cheong et al., GD22), called weak and strong fan-planarity, which separate two non-equivalent definitions of fan-planarity in t…
The thickness of fan-planar graphs is at most three
Otfried Cheong, Maximilian Pfister, Lena Schlipf
We prove that in any strongly fan-planar drawing of a graph G the edges can be colored with at most three colors, such that no two edges of the same color cross. This implies that…
Efficient Fréchet distance queries for segments
Maike Buchin, Ivor van der Hoog, Tim Ophelders +3
We study the problem of constructing a data structure that can store a two-dimensional polygonal curve , such that for any query segment one can efficiently comp…
One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons
Patrizio Angelini, Philipp Kindermann, Andre Löffler +2
We consider the problem of drawing an outerplanar graph with vertices with at most one bend per edge if the outer face is already drawn as a simple polygon. We prove that it ca…
Augmenting Geometric Graphs with Matchings
Alexander Pilz, Jonathan Rollin, Lena Schlipf +1
We study noncrossing geometric graphs and their disjoint compatible geometric matchings. Given a cycle (a polygon) P we want to draw a set of pairwise disjoint straight-line edges…
On Romeo and Juliet Problems: Minimizing Distance-to-Sight
Hee-Kap Ahn, Eunjin Oh, Lena Schlipf +2
We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points and in a simple polygon w…
Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles
Philipp Kindermann, Fabrizio Montecchiani, Lena Schlipf +1
We show that the 1-planar slope number of 3-connected cubic 1-planar graphs is at most 4 when edges are drawn as polygonal curves with at most 1 bend each. This bound is obtained b…
Convexity-Increasing Morphs of Planar Graphs
Linda Kleist, Boris Klemz, Anna Lubiw +3
We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one w…
On Gallai's conjecture for series-parallel graphs and planar 3-trees
Philipp Kindermann, Lena Schlipf, André Schulz
A path cover is a decomposition of the edges of a graph into edge-disjoint simple paths. Gallai conjectured that every connected -vertex graph has a path cover with at most $\lc…
Edge-Orders
Lena Schlipf, Jens M. Schmidt
Canonical orderings and their relatives such as st-numberings have been used as a key tool in algorithmic graph theory for the last decades. Recently, a unifying concept behind all…
Finding Largest Rectangles in Convex Polygons
Sergio Cabello, Otfried Cheong, Christian Knauer +1
We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with vertices. We…
Notes on Convex Transversals
Lena Schlipf
In this paper, we prove the problem of stabbing a set of disjoint bends by a convex stabber to be NP-hard. We also consider the optimization version of the convex stabber problem a…
Covering and Piercing Disks with Two Centers
Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer +3
We give exact and approximation algorithms for two-center problems when the input is a set of disks in the plane. We first study the problem of finding two smallest c…