Lena Schlipf
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
Research Subjects
Lena Schlipf has a total of 34 co-authors. Here are the top co-authors by number of shared publications:
- Antonios Symvonis
National Technical University of Athens, Athens, Greece
4 shared publications - Alexander Wolff
Universität Würzburg, Würzburg, Germany
3 shared publications - Eleni Katsanou
National Technical University of Athens Greece
3 shared publications - Henry Förster
Technical University of Munich, Munchen, Germany
3 shared publications - Maximilian Pfister
Universität Tübingen
3 shared publications - Otfried Cheong
SCALGO
3 shared publications
Latest Publications
- Open Access
- 16 November 2026
- Published by Springer Nature in Algorithmica
- Vol. 89 (1) , 3
Minimum Monotone Spanning Trees
Given a finite set S of points in the plane and a finite set $$\mathcal {D}$$ of directions, a geometric spanning tree T of S is $$\mathcal {D}$$ -monotone if every path in T is monotone with respect to some direction in $$\mathcal {D}$$ . We study the problem of computing, for a given point set S and a given set $$\mathcal {D}$$ of directions, a minimum-length $$\mathcal{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}$$ -monotone spanning tree of S over all possible sets $$\mathcal {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)$$ and $$O(n^6)$$ time for $$k=1$$ and $$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$$ and a set $$\mathcal {D}_k$$ of k directions such that any minimum-length $$\mathcal {D}_k$$ -monotone spanning tree of $$S_k$$ has maximum vertex degree 2 k .- 16 November 2026
- Published by Springer Nature in Algorithmica
- Vol. 89 (1) , 3
Open AccessMinimum Monotone Spanning Trees
Given a finite set S of points in the plane and a finite set $$\mathcal {D}$$ of directions, a geometric spanning tree T of S is $$\mathcal {D}$$ -monotone if every path in T is monotone with respect to some direction in $$\mathcal {D}$$ . We study the problem of computing, for a given point set S and a given set $$\mathcal {D}$$ of directions, a minimum-length $$\mathcal{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}$$ -monotone spanning tree of S over all possible sets $$\mathcal {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)$$ and $$O(n^6)$$ time for $$k=1$$ and $$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$$ and a set $$\mathcal {D}_k$$ of k directions such that any minimum-length $$\mathcal {D}_k$$ -monotone spanning tree of $$S_k$$ has maximum vertex degree 2 k . - 14 February 2026
- Published by Springer Nature
- p. 49-63
On Compaction and Realizability of Almost Convex Octilinear Representations
- 14 February 2026
- Published by Springer Nature
- p. 49-63
On Compaction and Realizability of Almost Convex Octilinear Representations
- Open Access
On Compaction and Realizability of Almost Convex Octilinear Representations
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.
Open AccessOn Compaction and Realizability of Almost Convex Octilinear Representations
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.
- Open Access
Minimum Monotone Spanning Trees
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 AccessMinimum Monotone Spanning Trees
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
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.
Open AccessWeakly and Strongly Fan-Planar Graphs
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.
- 19 January 2023
- Published by Springer Nature
- p. 247-260
The Thickness of Fan-Planar Graphs is At Most Three
- 19 January 2023
- Published by Springer Nature
- p. 247-260
The Thickness of Fan-Planar Graphs is At Most Three
- 1 January 2023
- Published by Springer Nature
- p. 209-221
On the 2-Layer Window Width Minimization Problem
- 1 January 2023
- Published by Springer Nature
- p. 209-221
On the 2-Layer Window Width Minimization Problem
- 23 December 2021
- Published by Springer Nature
- p. 184-192
One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons
- 23 December 2021
- Published by Springer Nature
- p. 184-192
One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons