LSLena Schlipf

Lena Schlipf

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Lena Schlipf has a total of 34 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Minimum Monotone Spanning Trees

    by Emilio Di Giacomo, Walter Didimo, Eleni Katsanou, Lena Schlipf, Antonios Symvonis, Alexander Wolff

    Given a finite set S of points in the plane and a finite set $$\mathcal {D}$$ D of directions, a geometric spanning tree T of S is $$\mathcal {D}$$ D -monotone if every path in T is monotone with respect to some direction in $$\mathcal {D}$$ D . We study the problem of computing, for a given point set S and a given set $$\mathcal {D}$$ D of directions, a minimum-length $$\mathcal{D}$$ D -monotone spanning tree of S . We present a quadratic-time algorithm for two directions. More generally, we show that the problem belongs to the complexity class XP when parameterized by the number of directions. We further study, for a given positive integer k and point set S , the problem of finding a minimum-length $$\mathcal {D}$$ D -monotone spanning tree of S over all possible sets $$\mathcal {D}$$ D of k directions. We prove that this problem, too, is in XP when parameterized by k , and present two algorithms that run in $$O(n^2 \log n)$$ O ( n 2 log n ) and $$O(n^6)$$ O ( n 6 ) time for $$k=1$$ k = 1 and $$k=2$$ k = 2 , respectively, where n is the number of points in S . Finally, in contrast to the classical Euclidean minimum spanning tree of a set of points, whose vertex degree is bounded by six, we show that for every even integer k , there exists a point set $$S_k$$ S k and a set $$\mathcal {D}_k$$ D k of k directions such that any minimum-length $$\mathcal {D}_k$$ D k -monotone spanning tree of $$S_k$$ S k has maximum vertex degree 2 k .

  • Open Access

    On Compaction and Realizability of Almost Convex Octilinear Representations

    by 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 problems where the input specifies a so-called representation, that is: a planar embedding; the angles occurring between adjacent edges; the bends along each edge. In Orthogonal Realizability one is asked to compute any orthogonal drawing satisfying the constraints, while in Orthogonal Compaction the goal is to find such a drawing using minimum area. While Orthogonal Realizability can be solved in linear time, Orthogonal Compaction is NP-hard even if the graph is a cycle. In contrast, already Octilinear Realizability is known to be NP-hard. In this paper we investigate Octilinear Realizability and Octilinear Compaction problems. We prove that Octilinear Realizability remains NP-hard if at most one face is not convex or if each interior face has at most 8 reflex corners. We also strengthen the hardness proof of Octilinear Compaction, showing that Octilinear Compaction does not admit a PTAS even if the representation has no reflex corner except at most 4 incident to the external face. On the positive side, we prove that Octilinear Realizability is FPT in the number of reflex corners and for Octilinear Compaction we describe an XP algorithm on the number of edges represented with a +1 or -1 slope segment (i.e., the diagonals), again for the case where the representation has no reflex corner except at most 4 incident to the external face.

  • Minimum Monotone Spanning Trees

    by Emilio Di Giacomo, Walter Didimo, Eleni Katsanou, Lena Schlipf, Antonios Symvonis, Alexander Wolff


  • Open Access

    Minimum Monotone Spanning Trees

    by Emilio Di Giacomo, Walter Didimo, Eleni Katsanou, Lena Schlipf, Antonios Symvonis, Alexander Wolff

    Computing a Euclidean minimum spanning tree of a set of points is a seminal problem in computational geometry and geometric graph theory. We combine it with another classical problem in graph drawing, namely computing a monotone geometric representation of a given graph. More formally, given a finite set $S$ of points in the plane and a finite set $\cal D$ of directions, a geometric spanning tree $T$ with vertex set $S$ is ${\cal D}$-monotone if, for every pair $\{u,v\}$ of vertices of $T$, there exists a direction $d \in \cal D$ for which the unique path from $u$ to $v$ in $T$ is monotone with respect to $d$. We provide a characterization of ${\cal D}$-monotone spanning trees. Based on it, we show that a ${\cal D}$-monotone spanning tree of minimum length can be computed in polynomial time if the number $k=|{\cal D}|$ of directions is fixed, both when (i) the set ${\cal D}$ of directions is prescribed and when (ii) the objective is to find a minimum-length ${\cal D}$-monotone spanning tree over all sets ${\cal D}$ of $k$ directions. For $k = 2$, we describe algorithms that are much faster than those for the general case. Furthermore, in contrast to the classical Euclidean minimum spanning tree, whose vertex degree is at most six, we show that for every even integer $k$, there exists a point set $S_k$ and a set $\cal D$ of $k$ directions such that any minimum-length $\cal D$-monotone spanning tree of $S_k$ has maximum vertex degree $2k$.

  • Open Access

    Weakly and Strongly Fan-Planar Graphs

    by Otfried Cheong, Henry Förster, Julia Katheder, Maximilian Pfister, Lena Schlipf

    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 the literature. We prove that not every weakly fan-planar graph is strongly fan-planar, while the upper bound on the edge density is the same for both families.

  • The Thickness of Fan-Planar Graphs is At Most Three

    by Otfried Cheong, Maximilian Pfister, Lena Schlipf


  • Weakly and Strongly Fan-Planar Graphs

    by Otfried Cheong, Henry Förster, Julia Katheder, Maximilian Pfister, Lena Schlipf


  • On the 2-Layer Window Width Minimization Problem

    by Michael A. Bekos, Henry Förster, Michael Kaufmann, Stephen Kobourov, Myroslav Kryven, Axel Kuckuk, Lena Schlipf


  • One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons

    by Patrizio Angelini, Philipp Kindermann, Andre Löffler, Lena Schlipf, Antonios Symvonis