This paper studies the problem of computing quasi-upward planar drawings of bimodal plane digraphs with minimum curve complexity, i.e., drawings such that the maximum number of bends per edge is minimized. We prove that every bimodal plane digraph ad
mits a quasi-upward planar drawing with curve complexity two, which is worst-case optimal. We also show that the problem of minimizing the curve complexity in a quasi-upward planar drawing can be modeled as a min-cost flow problem on a unit-capacity planar flow network. This gives rise to an $tilde{O}(m^frac{4}{3})$-time algorithm that computes a quasi-upward planar drawing with minimum curve complexity; in addition, the drawing has the minimum number of bends when no edge can be bent more than twice. For a contrast, we show bimodal planar digraphs whose bend-minimum quasi-upward planar drawings require linear curve complexity even in the variable embedding setting.
We study $k$-page upward book embeddings ($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on $k$ pages with the additional requirement that the vertices of the graph appear in a topological order
ing along the spine of the book. We show that testing whether a graph admits a $k$UBE is NP-complete for $kgeq 3$. A hardness result for this problem was previously known only for $k = 6$ [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on $k=2$. On the algorithmic side, we present polynomial-time algorithms for testing the existence of $2$UBEs of planar $st$-graphs with branchwidth $beta$ and of plane $st$-graphs whose faces have a special structure. These algorithms run in $O(f(beta)cdot n+n^3)$ time and $O(n)$ time, respectively, where $f$ is a singly-exponential function on $beta$. Moreover, on the combinatorial side, we present two notable families of plane $st$-graphs that always admit an embedding-preserving $2$UBE.
We initiate the study of 2.5D box visibility representations (2.5D-BR) where vertices are mapped to 3D boxes having the bottom face in the plane $z=0$ and edges are unobstructed lines of sight parallel to the $x$- or $y$-axis. We prove that: $(i)$ Ev
ery complete bipartite graph admits a 2.5D-BR; $(ii)$ The complete graph $K_n$ admits a 2.5D-BR if and only if $n leq 19$; $(iii)$ Every graph with pathwidth at most $7$ admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBR) which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an $n$-vertex graph that admits a 2.5D-GBR has at most $4n - 6 sqrt{n}$ edges and this bound is tight. Finally, we prove that deciding whether a given graph $G$ admits a 2.5D-GBR with a given footprint is NP-complete. The footprint of a 2.5D-BR $Gamma$ is the set of bottom faces of the boxes in $Gamma$.
In a emph{fan-planar drawing} of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt, who proved that every $n$-vertex fan-planar drawing has at most $5n-10$ edges,
and that this bound is tight for $n geq 20$. We extend their result, both from the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrain
