We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head, and the y-coordinates of the vertices are integers. The span of an edge in such a drawing is the absolute difference between the y-coordinates of its endpoints, and the span of the drawing is the maximum span of any edge. The span of an upward-planar graph is the minimum span over all its upward-planar drawings. We study the problem of determining the span of upward-planar graphs and provide both combinatorial and algorithmic results. On the combinatorial side, we present upper and lower bounds for the span of directed trees. On the algorithmic side, we show that the problem of determining the span of an upward-planar graph is NP-complete already for directed trees and for biconnected single-source graphs. Moreover, we give efficient algorithms for several graph families with a bounded number of sources, including st-planar graphs and graphs where the planar or upward-planar embedding is prescribed. Furthermore, we show that the problem is fixed-parameter tractable with respect to the vertex cover number and the treedepth plus the span.

In this paper, we test whether Multimodal Large Language Models (MLLMs) can match human-subject performance in tasks involving the perception of properties in network layouts. Specifically, we replicate a human-subject experiment about perceiving quality (namely stress) in network layouts using GPT-4o, Gemini-2.5 and Qwen2.5. Our experiments show that giving MLLMs the same study information as trained human participants yields performance comparable to that of human experts and exceeds that of untrained non-experts. Additionally, we show that prompt engineering that deviates from the human-subject experiment can lead to better-than-human performance in some settings. Interestingly, like human subjects, the MLLMs seem to rely on visual proxies rather than computing the actual value of stress, indicating some sense or facsimile of perception. Explanations from the models are similar to those used by the human participants (e.g., an even distribution of nodes and uniform edge lengths).

We present a novel approach to graph drawing based on reinforcement learning for minimizing the global and the local crossing number, that is, the total number of edge crossings and the maximum number of crossings on any edge, respectively. An agent learns how to move a vertex based on a given observation vector. The agent receives feedback in the form of local reward signals tied to crossing reduction. To generate an initial layout, we use a stress-based graph-drawing algorithm. We compare our method against force- and stress-based baseline algorithms as well as three established algorithms for global crossing minimization on a suite of benchmark graphs. The experiments show mixed results: our current algorithm is mainly competitive for the local crossing number.

A strengthened version of Harborth’s well-known conjecture - known as Kleber’s conjecture - states that every planar graph admits a planar straight-line drawing where every edge has integer length and each vertex is restricted to the integer grid. Positive results for Kleber’s conjecture are known for planar 3-regular graphs, for planar graphs that have maximum degree 4, and for planar 3-trees. However, all but one of the existing results are existential and do not provide bounds on the required grid size. We provide polynomial-time algorithms for computing crossing-free straight-line drawings of trees and cactus graphs with integer edge lengths and integer vertex position on polynomial-size integer grids. We also give an historic overview of planar straight-line graph drawing results.

A linear layout of a graph consists of a linear ordering of its vertices and a partition of its edges into pages such that the edges assigned to the same page obey some constraint. The two most prominent and widely studied types of linear layouts are stack and queue layouts, in which any two edges assigned to the same page are forbidden to cross and nest, respectively. The names of these two layouts derive from the fact that, when parsing the graph according to the linear vertex ordering, the edges in a single page can be stored using a single stack or queue, respectively. Recently, the concepts of stack and queue layouts have been extended by using a double-ended queue or a restricted-input queue for storing the edges of a page. We extend this line of study to edge-weighted graphs by introducing priority queue layouts, that is, the edges on each page are stored in a priority queue whose keys are the edge weights. First, we show that there are edge-weighted graphs that require a linear number of priority queues. Second, we characterize the graphs that admit a priority queue layout with a single queue, regardless of the edge-weight function, and we provide an efficient recognition algorithm. Third, we show that the number of priority queues required independently of the edge-weight function is bounded by the pathwidth of the graph, but can be arbitrarily large already for graphs of treewidth two. Finally, we prove that determining the minimum number of priority queues is NP-complete if the linear ordering of the vertices is fixed.

The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve. In the variant Constrained Level Planarity (CLP), each level $y$ is equipped with a partial order $\prec_y$ on its vertices and in the desired drawing the left-to-right order of vertices on level $y$ has to be a linear extension of $\prec_y$. Ordered Level Planarity (OLP) corresponds to the special case of CLP where the given partial orders $\prec_y$ are total orders. Previous results by Brückner and Rutter [SODA 2017] and Klemz and Rote [ACM Trans. Alg. 2019] state that both CLP and OLP are NP-hard even in severely restricted cases. In particular, they remain NP-hard even when restricted to instances whose width (the maximum number of vertices that may share a common level) is at most two. In this paper, we focus on the other dimension: we study the parameterized complexity of CLP and OLP with respect to the height (the number of levels). We show that OLP parameterized by the height is complete with respect to the complexity class XNLP, which was first studied by Elberfeld et al. [Algorithmica 2015] (under a different name) and recently made more prominent by Bodlaender et al. [FOCS 2021]. It contains all parameterized problems that can be solved nondeterministically in time $f(k) n^{O(1)}$ and space $f(k) \log n$ (where $f$ is a computable function, $n$ is the input size, and $k$ is the parameter). If a problem is XNLP-complete, it lies in XP, but is W[$t$]-hard for every $t$. In contrast to the fact that OLP parameterized by the height lies in XP, it turns out that CLP is NP-hard even when restricted to instances of height 4. We complement this result by showing that CLP can be solved in polynomial time for instances of height at most 3.

A \emph{mixed interval graph} is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph $G$, an interval $u$ receives a lower (different) color than an interval $v$ if $G$ contains arc $(u,v)$ (edge $\{u,v\}$). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. For coloring general mixed interval graphs, we present a $\min \{ω(G), λ(G)+1 \}$-approximation algorithm, where $ω(G)$ is the size of a largest clique and $λ(G)$ is the length of a longest directed path in $G$. For the subclass of \emph{bidirectional interval graphs} (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs. We introduce a new natural class of mixed interval graphs, which we call \emph{containment interval graphs}. In such a graph, there is an arc $(u,v)$ if interval $u$ contains interval $v$, and there is an edge $\{u,v\}$ if $u$ and $v$ overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring.

The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector, are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general NP-hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines (Q|HM|C_max) is NP-hard already with 6 job types, and that the related Cutting Stock problem is NP-hard already with 8 item types. For the more general unrelated machines model (R|HM|C_max), we show that if either the largest job size p_max, or the number of jobs n are polynomially bounded in the instance size |I|, there are algorithms with complexity |I|^poly(k). Our main result is that this is unlikely to be improved, because Q||C_max is W[1]-hard parameterized by k already when n, p_max, and the numbers describing the speeds are polynomial in |I|; the same holds for R|HM|C_max (without speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives 𝓁₂-norm minimization of the load vector and, partially, sum of weighted completion times ∑ w_j C_j. Along the way, we answer affirmatively the question whether makespan minimization on identical machines (P||C_max) is fixed-parameter tractable parameterized by k, extending our understanding of this fundamental problem. Together with our hardness results for Q||C_max this implies that the complexity of P|HM|C_max is the only remaining open case.