New Frontiers of Parameterized Complexity in Graph Drawing

The focus of the working group from the 2021 seminar was on the product structure theorem of Dujmovic, Joret, Micek, Morin, Ueckerdt, and Wood (J. ACM 2020). We were following two research directions, to find nontrivial direct algorithmic applications of the product structure theory (which do not seem to exist in this strict sense), and to suitably extend the scope of the product structure beyond planarity, while still giving explicit small bounds. We succeeded in the second direction as follows.

A graph is $h$-framed, if it admits a drawing in the plane whose uncrossed edges induce a biconnected spanning plane graph with faces of size at most $h$. For instance, every $1$-planar graph is a subgraph of a $4$-framed graph, and every $h$-framed graph is $O(h^2)$-planar. As the main result, we have proved:

We have used this theorem to improve known upper bounds on the queue number and the non-repetitive chromatic number on $1$-planar and optimal $2$-planar graphs, and to give explicit upper bounds on the twin-width of these graphs.

In Upward Planarity Testing, the input is a directed acyclic graph (DAG) $G$ and the question is whether there exists a planar drawing of $G$ such that all edges are drawn upward, i.e., all edges monotonically increase in the vertical direction. Upward Planarity Testing has been extensively studied in the literature, and arises naturally in a number of situations where the aim is to obtain easy-to-parse planar representations of DAGs. The problem has been shown to be NP-complete already 25 years ago [5], and there are a few special cases known when the problem can be solved in polynomial time. Among others, when $G$ is restricted to class of single-source DAGs [1], or the class of orientations of series-parallel graphs [4]. There have also been a couple of fixed-parameter tractability results for Upward Planarity Testing.

It was the goal of our working group at the previous edition of the seminar to push the boundaries Upward Planarity Testing from the parameterized complexity perspective, generalizing and unifying the previous results. Our first target was to generalize the polynomial-time single-source algorithm [1], which resulted in a single-exponential $\mathrm{𝖥𝖯𝖳}$ algorithm when parameterized by the number of sources [2]. We also considered the problem parameterized by prominent structural parameters. We showed that Upward Planarity Testing is $\mathrm{𝖷𝖯}$ parameterized by treewidth, and $\mathrm{𝖥𝖯𝖳}$ parameterized by treedepth of the underlying undirected graph [2]. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Finally, we used our improved analysis on the series-parallel case: We showed that Upward Planarity Testing can be solved in time $O(n^2)$ on $n$-vertex series-paralled graphs [3], while the previous-best algorithm runs in time $O(n^4)$ [4].

Orthogonal graph drawings are used in applications such as UML diagrams, VLSI layout, cable plans, and metro maps. We focus on drawing planar graphs and assume that we are given an orthogonal representation that describes the desired shape, but not the exact coordinates of a drawing. Our aim is to compute an orthogonal drawing on the grid that has minimum area among all grid drawings that adhere to the given orthogonal representation.

This problem is called orthogonal compaction (OC) and is known to be $\mathrm{𝖭𝖯}$-hard, even for orthogonal representations of cycles [1]. We investigate the complexity of OC with respect to several parameters. Among others, we show that OC is fixed-parameter tractable with respect to the most natural of these parameters, namely, the number of kitty corners of the orthogonal representation: the presence of pairs of kitty corners in an orthogonal representation makes the OC problem hard. Informally speaking, a pair of kitty corners is a pair of reflex corners of a face that point at each other. Accordingly, the number of kitty corners is the number of corners that are involved in some pair of kitty corners.

A flat clustered graph (for short flat c-graph) is a pair $(G,𝒱)$ where $G$ is a graph and $𝒱$ is a partition of the vertices of $G$. The parts of $𝒱$ are called clusters. A flat c-graph is independent if each of its clusters induces an independent set. Given a family $ℱ$ of connected graphs and an independent flat c-graph $𝒞=(G,𝒱=\{V_1,\mathrm{\dots },V_k\})$, the Planar $ℱ$-Augmentation problem for $𝒞$ asks to test for the existence of sets $Z_1,\mathrm{\dots },Z_k$ of non-edges of $G$ such that $G\cup {\bigcup }_{i=1}^k{Z}_i$ is planar and $G(V_i,Z_i)\in ℱ$ for $i=1,\mathrm{\dots },k$. If $ℱ$ is the family of all paths, then the problem coincides with the Clustered Planarity with Linear Saturators problem, which is known to be NP-complete [1]. On the other hand, if $ℱ$ is the family of all trees, then the problem coincides with the Clustered Planarity problem, which has been recently shown to be solvable in polynomial time [2].

We highlight some interesting research directions in the study of the Planar $ℱ$-augmentation problem. First, concerning the setting in which $ℱ$ is the set of all paths, the mentioned NP-completeness stimulates the search for exact parameterized and sub-exponential algorithms for the problem, both in the fixed and in the variable embedding setting. Moreover, albeit the problem is known to be NP-complete if all clusters, except one, are trivial, i.e., they each consist of a single vertex, it is still unknown whether the problem is para-NP-hard in the total number of clusters. Finally, as paths and trees may have linear radius, we regard as an appealing question, at the other side of the radius spectrum, to settle the complexity of the problem when $ℱ$ is the family of all stars. In this latter setting, it is possible to show that the problem reduces to a constrained planarity problem on the graph obtained by identifying all the vertices belonging to the same cluster, whose study may be of independent interest.

Witness graphs are a generalization of proximity graphs introduced by Aronov, Dulieu, and Hurtado [1]. A witness graph $G=(V,E)$ is defined by a quadruple $(P,S,W,\pm )$: $P$ is a set of points in plane and $V=P$; $S$ provides the geometric shapes (disks, squares, rectangles); $W$ is set of “witness” points/witnesses in plane; and $uv\in E$ if and only if

• $\mathrm{■}$

  if $+$: some $s\in S$ covers $u,v,w$ for some $w\in W$

• $\mathrm{■}$

  if $-$: some $s\in S$ covers $u,v$, but no $w\in W$

Examples of witness graphs include:

• $\mathrm{■}$

  Any Delaunay Triangulation can be defined as $(P,S,P,-)$, with $S$ being the set of all disks.

• $\mathrm{■}$

  $(P,S,\mathrm{\varnothing },-)$ defines a complete graph on $P$ as the vertex set.

• $\mathrm{■}$

  Witness Gabriel Graphs [2] are defined by $(P,S,W,-)$, where $S$ contains disks for pairs $u,v\in P$, such that $uv$ is diameter.

Spanning trees, in particular, depth-first spanning trees (DFS-trees) are popular tools in graph drawing. For these purposes, it may be convenient to consider DFS-trees with additional properties like minimum/maximum number of leaves or minimum height. The additional constraints usually make finding such trees NP-hard. The investigation of the parameterized complexity of problems of this type was initiated by Fellows, Friesen, and Langston [1]. We are interested in the parameterized complexity of Min Height DFS-Tree problem whose task is, given a graph $G$ and an integer $h$, to decide whether $G$ has a DFS-tree of height at most $h$. This problem is known to be NP-complete [1]. It can be observed that if $G$ has a DFS-tree of height at most $h$ then the treedepth of $G$ is upper bounded by $h$. This implies that Min Height DFS-Tree is $\mathrm{𝖥𝖯𝖳}$ when parameterized by $h$. Is it possible to give an efficient, say, single-exponential direct algorithm for the problem? Another direction of research is to investigate the (parameterized) approximability of the minimum height of a DFS-tree.

One of the most classically important features of graph drawings is a small number of crossings and the Crossing Number problem, which asks for the minimum number of crossings a graph can be drawn with , is arguably the most famous graph drawing problem. A driving motivation of the field of graph drawing is the visualisation of graphs – a task which is ubiquitous in areas such as the analysis of social networks, bioinformatics and linguistics or generally when information can be captured by graphs. Often such information can evolve over time and hence the treatment of temporal aspects is an important challenge in graph drawing. In particular, is reasonable to require some “stability” of drawing of a graph that changes over time in the sense that parts of the graph occur in consecutive time steps are not redrawn in a different way.

Motivated by this, we define the Sequential Crossing Number problem as generalisation of Crossing Number in which, given a sequence of graphs, we want to draw each of them in a way that drawings of intersections of consecutive graphs agree, and the total number of crossings (i.e. the sum of the number of crossings in each drawing) is minimised.

For $i\in [t-1]$ we say that $G_i$ and $G_{i+1}$ are consecutive. Let us also point out two alternative objectives that could be motivated in the same spirit: Instead of requiring ${\sum }_{i\in [t]}\text{crn}({𝒢}_i)\le k$, it could also be interesting to require ${\max }_{i\in [t]}\text{crn}({𝒢}_i)\le k$, i.e. minimise the maximum number of crossings in any graph, or ${\sum }_{i\in [t]}\text{crn}({𝒢}_i)-\text{crn}({{𝒢}_i|}_{G_i\cap G_{i-1}})\le k$, i.e. minimise the total number of crossings but counting crossings the drawing of the intersection of consecutive graphs only once.

Of course, classic Crossing Number is captured by $t=1$, and this already implies $\mathrm{𝖭𝖯}$-hardness of the problem. This is why our open problems will target parameterised algorithms for Sequential Crossing Number. Unless specified otherwise, we consider the parameterisation by $k$.

Sequential Crossing Number is closely related to the Simultaneous Crossing Number problem [1] which was proposed as a natural generalisation of the well-known Simultaneous Embedding with Fixed Edges problem ($t$-SEFE for short and most prominently considered for $t=2$) [2], but has not received a lot of attention since. The conceptual difference between Sequential Crossing Number and Simultaneous Crossing Number is that the former ensures stability of the drawings of subgraphs as long as they appear, whereas the latter additionally ensures stability of drawings of subgraphs that may disappear and reappear over time. $t$-SEFE is equivalent to Simultaneous Crossing Number for $k=0$.

Both problems are, by definition equivalent as soon as there is some graph $H$ such that $\forall i\in [t-1]G_i\cap G_{i+1}=H$. In particular, this means that the known $\mathrm{𝖭𝖯}$-hardness for $t$-SEFE on such instances, even if $t=3$ and $H$ is a star implies that we cannot hope for a parameterised (even $\mathrm{𝖷𝖯}$) algorithm for Sequential Crossing Number in $k+t$, even on instances with a common pairwise intersection of consecutive graphs which is a star.

We pose the general open problem:

We propose two concrete directions for such conditions: In the special case that $k=0$ and each intersection of consecutive graphs is 3-connected, the Sequential Crossing Number is equivalent to testing the planarity of each graph, and hence polynomial-time solvable. Moreover, branching and rigidising the drawings of intersections of consecutive graphs which contain crossings and branching on the graphs whose drawings contain crossings involving edges outside of any consecutive intersection in a hypothetical solution reduces Sequential Crossing Number on instances in which the pairwise intersections of consecutive graphs are 3-connected to Partially Predrawn Crossing Number (the problem of deciding the minimum number of crossings required to extend a drawing of a subgraph to the entire graph). Partially Predrawn Crossing Number is known to be in $\mathrm{𝖥𝖯𝖳}$ [3]. From this it can be argued that Sequential Crossing Number on instances in which the pairwise intersections of consecutive graphs are 3-connected is in $\mathrm{𝖷𝖯}$.

A similar idea would be to rigidise branched drawings for small intersections of consecutive graphs which could yield an $\mathrm{𝖷𝖯}$-algorithm for Sequential Crossing Number parameterised by $k+t+{\max }_{i\in [t-1]}|E(G_i\cap G_{i+1})|$.

In a different direction polynomial-time algorithm known for $t$-SEFE on instances with a common pairwise intersection of all input graphs requires that the pairwise intersection of graphs be 2-connected. It would be interesting to extend this result:

The concept of a left-aligned BFS tree of a planar graph, defined below, was formulated by P. Hliněný while working on an upper bound on the twin-width of planar graphs. It is an important ingredient in the currently best such bound of 8 by Hliněný and Jedelský (briefly noting, without left-aligned BFS trees the same proof would yield only an upper bound of 11). A left-aligned BFS tree can be computed in linear time for a given planar embedding. The featured question (or open problem) is whether the concept of a left-aligned BFS tree can find other applications in algorithmic problems related to planarity, and in particular in the graph drawing area.

We remark that this concept might seem closely related to the previously used leftist canonical ordering of planar graphs by Badent, Baur, Brandes, and Cornelsen, but it is not that close since the latter does have have the BFS property. Yet, possible applications of both notions may lie in similar areas.

A directed graph $G$ is an $st$-planar graph if it admits a planar embedding such that: (i) it contains no directed cycle; (ii) it contains a single source vertex $s$ and a single sink vertex $t$; and (iii) $s$ and $t$ both belong to the outer face of the planar embedding. A popular result in graph drawing states that a directed acyclic graph (DAG) $G$ has an upward planar drawing if and only if $G$ is a subgraph of an $st$-planar graph. Since testing upward planarity is NP-complete, it follows that testing if a graph is a subgraph of an $st$-planar graph is also hard. On the other hand, checking if a DAG is $st$-planar can be easily done in polynomial time.

Based on this motivation we propose to study the $st$-Planar Graph Augmentation Problem (stPA), which is defined as follows. Let $G=(V,E)$ be a DAG, and let $k$ be a positive integer. Is it possible to add at most $k$ edges to $G$ such that the resulting graph is an $st$-planar graph up to the addition of a super source $s$ and of a super sink $t$ in the outer face of the graph? As a natural open problem, we ask whether stPA admits a fixed-parameter tractable algorithm when parameterized in its natural parameter $k$.

The Queue Number of an undirected graph $G$ is the minimum number of pages $h$ such that $G$ has s $h$-queue layout (see also https://en.wikipedia.org/wiki/Queue_number).

An $h$-queue layout of $G=(V,E)$ is an ordering of the vertices together with a partition $𝒫$ of the edge set of $G$ into $h$ sets such that for every $P\in 𝒫$, if the vertices of $G$ are drawn on the line according to the ordering , then no two edges in $P$ form a rainbow, i.e., there are no two edges$e=(u,v)$ and $e=(x,y)$ in P such that . The following is known about Queue Number:

• $\mathrm{■}$

  NP-complete even for one page.

• $\mathrm{■}$

  polynomial-time for fixed ordering (due to $k$-rainbow obstructions)

• $\mathrm{■}$

  For one page: known to be fpt by treedepth [1]

• $\mathrm{■}$

  $\mathrm{𝖥𝖯𝖳}$ by vertex cover for arbitrary number of pages

Open Problems:

• $\mathrm{■}$

  For one page: $\mathrm{𝖥𝖯𝖳}$ by treewidth or feedback edge number?

• $\mathrm{■}$

  For arbitrary number of pages: $\mathrm{𝖥𝖯𝖳}$ by feedback edge number, treedepth, treewidth?

In Upward Planarity Testing, the input is a directed acyclic graph (DAG) $G$ and the question is whether there exists a planar drawing of $G$ such that all edges are drawn upward, i.e., all edges monotonically increase in the vertical direction. Upward Planarity Testing has been extensively studied, and was shown to be $\mathrm{𝖭𝖯}$-complete already 25 years ago [1], while many polynomial-time algorithms in special cases were also known.

As an outcome of the previous edition of the seminar, it has been shown that Upward Planarity Testing admits an algorithm with running time $n^{O(\mathrm{tw})}$ [2], where $n$ is the number of vertices in the graph and $\mathrm{tw}$ is its treewidth. In parameterized complexity terms, Upward Planarity Testing is thus in $\mathrm{𝖷𝖯}$ when parameterized by the treewidth of the underlying undirected graph.

A natural question is then whether the algorithmic result above can be improved. Specifically, is Upward Planarity Testing $𝖶$[1]-hard or $\mathrm{𝖥𝖯𝖳}$ parameterized by treewidth? If the former holds, is the running time of $n^{O(\mathrm{tw})}$ tight. For example, can it be shown that there is no $n^{o(\mathrm{tw})}$-time algorithm under the ETH?

Graph drawing is about finding embeddings of graphs in low-dimensional space. I proposed to look at the embedding problem from a new angle, namely, from a machine-learning point of view. In machine learning, embeddings are also mappings into a low-dimensional space, that represents a condensed form of information, from a high-dimensional space, such as the space of human-written documents or the space of graphs from an application area. The goals of the classical embedding in graph drawing and embedding in machine learning are related, but different: In graph drawing, we usually aim for readability by, e.g., minimizing the number of crossings. In machine learning, we aim to embed similar entities (such as Dagstuhl open problem descriptions) close to each other in the embedding space. A famous embedding algorithm in the machine-learning realm is Node2vec [1], which aims to map the vertex set of a given graph to a low-dimensional embedding space such that similar vertices, as measured by a certain neighborhood relation based on co-occurrence in random walks, are close to each other in the embedding space.

It seems interesting to:

1. 1.

   Explore machine-learning embedding problems from a visualization point of view, i.e., is a graph easier to understand if we embed similar vertices close to each other in 2d-space, like in Node2vec?

2. 2.

   Consider discrete variants of embedding problems: The dimensions in the embedding space can be thought of as underlying features of the data. For interpretability, it would be desirable to have few easy-to-understand features. I.e., it would be interesting to map to low-dimensional spaces where each dimension has only small domain, that is, a small number of admissible values.

3. 3.

   Develop efficient algorithms that exploit properties such as the low dimensionality of the embedding space, small domains, and input graph structure.

For a concrete starting point, we may look at a simplified version of Node2vec: Here, we are given a graph $G=(V,E)$ and we aim to find a mapping $f:V\to {ℝ}^d$ for some small $d$ such that ${\sum }_{u\in V}\log \text{Pr}(N(u)\mid f(u))$ is maximized. Intuitively and simplified, we want to maximize the number of vertices with the same neighborhood that are mapped to the same point in the embedding space. After several approximations, Grover and Leskovec [1] arrive at the objective to maximize

where $Z_u={\sum }_{v\in V}\exp (f(u)f(v))$. Herein, we can think of the logarithmic term as a baseline and each term in the sum measures the deviation from the baseline. Simplifying further, we may observe that in the vertices in the baseline term are weighed lower (due to taking the logarithm) than the vertices in the other term. If we weigh both at exactly half instead, we obtain the following objective:

For instance, if we simply want to find an embedding into binary, one-dimensional space $\{0,1\}$, we thus want to find an induced subgraph (corresponding to the vertices assigned 1) that maximizes the number of edges contained in the subgraph minus the number of nonedges in the subgraph. A natural first step is to find some baseline complexity results or promising algorithms by looking at such special cases and then generalize to larger domains and dimensions.

Hypergraphs [1] are not only theoretically interesting as a generalized notion of graphs, but also has a wide range of applications in many fields, such as database theory, biology, and so on [3]. Therefore, drawing and visualizing hypergraphs is useful for understanding practical cases in applied fields.

Examples of such visualized hypergraphs have been appeared in typical textbooks or papers [1, 2], however, there are many different ways to draw them, and a unified approach has not yet been fully established. On the other hand, it is often experienced that the level of understanding a hypergraph varies greatly depending on how it is drawn, and there is a need for “nice” drawing of hypergraphs.

The criteria for goodness or understandability of a hypergraph drawing could simply be the number of crossings of hyperedges or the number of curved lines, for example, but the definition of the crossings itself is not necessarily trivial that might be depending on the drawing model. Thus, for example, the following kind of problem can be considered:

Minimum Number of Curved Lines
Input: a $k$-uniform hypergraph $(k\ge 3)$,
Output: under “straight and curved line model”, what is the minimum number of curved lines, and what is its node layout?

We would then like to discuss drawing algorithms that optimize such criteria and analyze these algorithms in terms of their parameterized computational complexity. Possible parameters include the number of hyperedges, the number of crossings, the maximum degree, uniformity, and so on.

This topic is closely related to the notion of set visualization, e.g., https://www.dagstuhl.de/en/seminars/seminar-calendar/seminar-details/22462, so we have to scrutinize the results in that field.

A flat clustered graph (for short flat c-graph) is a pair $(G,𝒱)$ where $G$ is a graph and $𝒱$ is a partition of the vertices of $G$. The parts of $𝒱$ are called clusters. A flat c-graph is independent if each of its clusters induces an independent set. Given a family $ℱ$ of connected graphs and an independent flat c-graph $𝒞=(G,𝒱=\{V_1,\mathrm{\dots },V_k\})$, the Planar $ℱ$-augmentation problem for $𝒞$ asks to test for the existence of sets $Z_i$ of edges joining pairs of vertices in $V_i$ for $i=1,\mathrm{\dots },k$, such that $G\cup {\bigcup }_{i=1}^k{Z}_i$ is planar and $G(V_i,Z_i)\in ℱ$ for $i=1,\mathrm{\dots },k$. If $ℱ$ is the family of all paths, then the problem coincides with the Clustered Planarity with Linear Saturators problem, which is known to be NP-complete [1]. On the other hand, if $ℱ$ is the family of all trees, then the problem coincides with the Clustered Planarity problem, which has been recently shown to be solvable in polynomial time [2].

We consider Planar $ℱ$-augmentation for two classes $ℱ$, i.e., the set $𝒫$ of all paths and the set $𝒮$ of all stars. Since it is known that Planar $𝒫$-augmentation is NP-hard even if the input graph has no edges, but has many non-trivial clusters (clusters containing more than one vertex), we tried to obtain an fpt-algorithm for the parameter treewidth plus the number of non-trivial clusters using SPQR-trees. Unfortunately, after some consideration, we had to abandon this approach, after realizing that we were not able to handle spiralling paths in the solution; see also Figure 4b) in [3] giving a worst-case example for spiralling paths.

We then focused on obtaining exact algorithms for Planar $𝒫$-augmentation and we are now pretty confident that we can obtain a single-expoential $2^{O(n)}$ algorithm for the problem in the variable embedding case as well as a subexponential $2^{O(\log n\sqrt{n})}$ algorithm in the fixed embedding case (if the initial graph is connected). Both algorithms start by guessing a separator of the solution graph. Then, in the variable embedding case we additionally guess the partition of the separation (which dominates the run-time in this case and is the reason that we do not obtain a subexponential-time algorithm). After doing so the algorithm proceeds recursively in both parts. In the fixed embedding and connected case, we can circumvent guessing the partition, by guessing the curve through the separator, which leaves only $n^{\sqrt{n}}=2^{O(\log n\sqrt{n})}$ many choices. We leave it open whether either the variable-embedding case can be improved to a subexponential-time algorithm and whether we can avoid the $\log n$ factor in the exponent for the fixed-embedding case.

Our second main result concerns the Planar $𝒮$-augmentation problem. Here, we can show that if the input graph is bi-connected, then Planar $𝒮$-augmentation can be solved in polynomial-time in the variable-embedding case. The main ideas behind this algorithm are as follows. Consider the graph $H$ obtained from $G$ after contradicting every cluster into a single vertex such that every half-edge in $H$ is assigned the color that is equal to the vertex in the cluster that it originated from. Our first observation is that $G$ has a solution if and only if $H$ has a drawing such that all but one color of the half-edges around every vertex is consecutive. In other words there is at most one color that is split at every vertex. We now employ a dynamic programming algorithm along an SPQR-tree of $H$ to decide whether $H$ admits such a drawing. To do so we define the following records for every pertinent graph corresponding to an artificial arc $st$: a record stores the colors of the two outermost half-edges incident to $s$, the colors of the two outermost half-edges incident to $t$, and the color that is split (if there is no split color this remains undefined). It is important to note that every pertinent graph $st$ has at most $3$ colors that also occur outside (otherwise at least two colors are split and there is no solution for $H$) and that we do not need to know the identity of any color that does not occur outside. Therefore, the number of possible colors that we store for every entry of the record is at most $4$, i.e., the color could be one of the at most $3$ colors that also occur outside or it could be another color (which we will denote with the symbol $u$). Therefore, the number of records for a pertinent graph is at most $4^4+5$ ($4$ options for the colors of the outer half-edges and $5$ options for the split color). It is then relatively straightforward to show how the records are computed for $S$-nodes. For $P$-nodes, we design a slightly more involved greedy algorithm that guesses the colors of the outer half-edges and then proceeds by computing the forced implications. Rather more complicated is the algorithm for computing $R$-nodes. Here, we manage to obtain an encoding into $2$-SAT after some preprocessing of the instance. It is not clear to us how to get around the condition that $G$ has to be bi-connected. Neither do we know, whether a similar approach can be used for the fixed-embedding case. The main problem with using our approach for the fixed embedding case is that our initial observation about contradicting every cluster into one vertex does not longer preserve solutions. This is because the color that is split at any vertex depends on, where the contracted vertex is placed within the drawing.

A plane digraph $G$ is a directed planar graph with a given planar embedding. In particular, the embedding of $G$ defines the circular ordering of the edges incident to each vertex. A vertex $v$ of $G$ is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around $v$. A plane digraph is bimodal if all its vertices are bimodal. For example, the plane digraph of Figure 2(a) is not bimodal, namely the vertices $3,4,5,7$ are bimodal while the vertices $1,2,6$ are not.

Bimodality is a central property for many graph drawing styles. In particular, it is a necessary condition for the existence of level-planar and upward planar drawings, where the edges are represented as curves monotonically increasing in the upward direction according to their orientations [11, 12, 13, 18]. Bimodality becomes also a sufficient condition for the existence of embedding-preserving quasi-upward planar drawings, in which edges are allowed to violate the upward monotonicity a finite number of times at points called bends [5, 6, 7]. Recently, it has been shown that bimodality is also sufficient for the existence of planar L-drawings of digraphs, in which distinct L-shaped edges may overlap but not cross [1, 2, 3].

Given a digraph $G$ it is possible to decide in linear time if $G$ admits a bimodal planar embedding, by simply transforming the problem into a planarity testing problem on a suitable digraph obtained by splitting each non-bimodal vertex of $G$ into two vertices [5]. However, when $G$ is not bimodal, a problem that naturally arises is to extract from $G$ a subgraph of maximum size (i.e., with the maximum number of edges) that is bimodal. Unfortunately, this problem is known to be NP-hard, even when $G$ has a given planar embedding and we look for an embedding-preserving maximum bimodal subgraph [8]. This problem is called the Maximum Bimodal Subgraph (MBS) problem. For example, Figure 2(b) shows a bimodal subgraph of maximum size for the graph of Figure 2(a).

Binucci et al. [8] describe a heuristic and an exponential-time branch-and-bound algorithm to solve MBS, by also addressing the more specific problem of extracting from the input plane digraph $G$ an upward planar digraph of maximum size.

During the Dagstuhl Seminar we studied the MBS problem from the parameterized complexity and approximability perspectives (we refer to the books [10, 15] for an introduction to the parameterized complexity area). More precisely, we considered the following more general version of the problem with weighted edges, which coincides with MBS if we restrict to unit edge weights.

MWBS$(G,w)$ (Maximum Weighted Bimodal Subgraph). Given a plane digraph $G$ and an edge-weight function $w:E(G)\to {\mathbb{Q}}^{+}$, compute a bimodal subgraph of $G$ of maximum weight, i.e., whose sum of the edge weights is maximum over all bimodal subgraphs of $G$.

We studied different parameters for the MWBS$(G,w)$ problem and mainly focused on the following: $(i)$ the number $b$ of non-bimodal vertices of the input graph $G$, which intrinsically captures the nature and the difficulty of the problem; $(ii)$ the branchwidth and the treewidth of the undirected underlying graph of $G$, which are structural parameters commonly adopted in parameterized complexity. Our main results can be summarized as follows.

• $\mathrm{■}$

  Structural parameterization. We show that MWBS is $\mathrm{𝖥𝖯𝖳}$ when parameterized by the branchwidth of the input digraph $G$ or, equivalently, by the treewidth of $G$, which is correlated to the branchwidth by a constant factor [19]. Our algorithm deviates from a standard dynamic approach for graphs of bounded treewidth. Since we have to incorporate the “topological” information about the given embedding in the dynamic program, we exploit the sphere-cut decomposition of Dorn et al. [14].

• $\mathrm{■}$

  Kernelization. We prove the existence of a polynomial kernel for the decision version of MWBS parameterized by the number $b$ of non-bimodal vertices. Our kernelization consists of several steps. First we show how to reduce the instance to an equivalent instance whose branchwidth is $O(\sqrt{b})$. Second, by using specific gadgets, we compress the problem to an instance of another problem whose size is bounded by a polynomial of $b$. Finally, by the standard arguments, [15, Theorem 1.6], based on a polynomial reduction between any NP-complete problems, we obtain a polynomial kernel for MWBS.

  By pipelining the crucial step of the kernelization algorithm with the branchwidth algorithm, we obtain a parameterized subexponential algorithm for MWBS of running time $2^{O(\sqrt{b})}\cdot n^{O(1)}$. Since $b\le n$, this also implies an algorithm of running time $2^{O(\sqrt{n})}$. We remark that our algorithms are asymptotically optimal up to the Exponential Time Hypothesis (ETH) [16, 17]. The NP-hardness result of MBS (and hence of MWBS) given in [8] exploits a reduction from Planar-3SAT. The number of non-bimodal vertices in the resulting instance of MBS is linear in the size of the Planar-3SAT instance. Using the standard techniques for computational lower bounds for problems on planar graphs [10], we obtain that the existence of an $2^{o(\sqrt{b})}\cdot n^{O(1)}$-time algorithm for MBWS would contradict ETH.

• $\mathrm{■}$

  Approximability. We provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for MWBS, based on Baker’s (or shifting) technique [4]. More precisely, using our algorithm for graphs of bounded branchwidth, we give an $(1+ϵ)$-approximation algorithm that runs in $2^{O(1/ϵ)}\cdot n^{O(1)}$ time.

A natural future research direction is to extend our study to a generalization of bimodality, called $k$-modality. Given a positive even integer $k$, a plane digraph is $k$-modal if the edges at each vertex can be grouped into at most $k$ sets of consecutive edges with the same orientation [20]. For example, it is known that $4$-modality is necessary for planar L-drawings [9].

A driving motivation of the field of graph drawing is the visualisation of information that can be captured by graphs. Often such information can evolve over time and hence the treatment of temporal aspects is an important challenge in graph drawing. In this context it makes sense to require some “stability” of the drawing of a graph that changes over time in the sense that parts of the graph continue to occur in consecutive time steps are not redrawn in a different way. Motivated by this we define the following crossing-minimal drawing variant. Below $\mathrm{cr}(𝒢)$ for a drawing $𝒢$ of a graph denotes the number of edge crossings in the drawing.

Sequential Crossing Number (SCN):

Problem: A sequence $G_1,G_2,\mathrm{\dots },G_t$ of (in general non-disjoint) graphs, an integer $k$.

Question: Is there a drawing ${𝒢}_i$ of each $G_i$ such that for each $i\in [t-1]$ we have

SCN is obviously more general than the classical crossing number problem, which corresponds to the setting in which $t=1$, and it is also more general than the partially predrawn crossing number problem [5] which can be captured using $t=2$, having as $G_1$ the rigidised (also adding many parallel edges) prescribed partial drawing of the graph and as $G_2$ the graph to which the partial predrawing should be extended.

Moreover, in the special case that for all $i,j\in [t]$, $G_i\cap G_j={\bigcap }_{\mathrm{\ell }\in [t]}{G}_i$, i.e. the pairwise intersection of all given graphs is the same, then we speak of sunflower instances, and refer to ${\bigcap }_{\mathrm{\ell }\in [t]}{G}_i$ as the core (in line with terminology used for Simultaneous Embedding with Fixed Edges (SEFE) [2]). On sunflower instances, SEFE and SCN with $k=0$ are easily seen to be completely equivalent.

Indeed, there is even a simple reduction from SEFE on general (not necessarily sunflower) instances to SCN with $k=0$ by considering, for an input $G_1,\mathrm{\dots },G_t$ of SEFE, the instance of SCN (on sunflower instances) given by $G_{\mathrm{\ell }}\cup {\bigcup }_{i,j\in [t]}{G}_i\cap G_j$, for $\mathrm{\ell }\in [t]$, and $k=0$.

From the known hardness of SEFE on sunflower instances with $t=3$ and the core being a star[1], we obtain the following.

A generalisation of SEFE to allow for drawings with crossings in which the total number of crossings over any single graph is considered as the decision value has been proposed as Simultaneous Crossing Number [3], and can be reduced to SCN (with general $k$) in the same way. Of course, since both problems are $\mathrm{𝖭𝖯}$-complete, there is also a polynomial reduction from SCN to the simultaneous crossing number problem. However, a difference between both reductions is that, in the direction from Simultaneous Crossing Number to SCN, we never increase the structural complexity of the union of all instance graphs, whereas this is necessary in the direction from SCN to Simultaneous Crossing Number to allow for ‘reappearing’ parts of graphs to be drawn differently.

SCN with $k=0$ also generalises planarity of streamed graphs [4]. A streamed graph with time window $w\in \mathbb{N}$ and backbone is given by a vertex set $V$, a set of edges $B$ on $V$ called a backbone, and an ordered non-repeating sequence of edges $e_1,\mathrm{\dots },e_m$ on $V$ which are not in $B$. By definition, this streamed graph is planar if and only if the following is a yes-instance for SCN with $k=0$: For $t=m$ and for $i\in [t]$, .

From the hardness result for testing planarity of streamed graphs with time window $5$ and empty backbones [4] we can infer the following for SCN.

In view of the above hardness results, our main target during the seminar was to formulate parameterised algorithms for SCN. Notably, we believe to be able to give the following results.

1. 1.

   SCN parameterised by $k+{\max }_{i\in [t-1]}|V(G_i)\cap V(G_{i+1})|$ is in $\mathrm{𝖥𝖯𝖳}$.

2. 2.

   SCN parameterised by $k$ is in $\mathrm{𝖷𝖯}$ on inputs in which for all $i\in [t-1]$, $G_i\cap G_{i+1}$ is $3$-connected. (This is subsumed by the next $\mathrm{𝖥𝖯𝖳}$ result but also used in its proof with $k=0$.)

3. 3.

   SCN parameterised by $k$ is in $\mathrm{𝖥𝖯𝖳}$ on inputs in which for all $i\in [t-1]$, $G_i\cap G_{i+1}$ is $3$-connected.

4. 4.

   SCN parameterised by $k+t+r$ is in $\mathrm{𝖥𝖯𝖳}$, where $r$ is an upper bound on the maximum number of bridges of a P-node in the SPQR-tree and the maximum degree of a vertex in the block cut tree of the intersection of two consecutive input graphs, on instances in which for all $i\in [t-1]$, $G_i\cap G_{i+1}$ is connected.

   • $\mathrm{■}$

     Notice that for $3$-connected consecutive intersections, $r=0$ and the condition is obviously satisfied. The only reason that this result does not subsume the $\mathrm{𝖥𝖯𝖳}$-result for $3$-connected consecutive intersections is the additional parameterisation on $t$.

   • $\mathrm{■}$

     The hardness from Theorem 1 implies that we cannot hope to drop $r$ – the maximum degree of a vertex in the block cut tree of the intersection of two consecutive input graphs, from the problem parameter.

In terms of techniques, the first two results are achieved by dynamic programming and branching algorithms, respectively, the former of which we briefly sketch:

We carry out dynamic programming on $t$, where the dynamic programming table is indexed by pairs of a drawing of $G_{i-1}\cap G_i$ and a drawing of $G_i\cap G_{i+1}$ with at most $k$ crossings in total. The number of such pairs of drawings is easily seen to be bounded in the considered parameter. Each table entry stores the minimum total number of crossings so far (using the state from the previous dynamic programming step) under the condition that the drawing of $G_i$ coincides with the index-prescribed drawings of $G_{i-1}\cap G_i$ and $G_i\cap G_{i+1}$. To compute an entry for a table index we use the $\mathrm{𝖥𝖯𝖳}$-algorithm for partially predrawn crossing number [5]. ∎

The second two results are far more involved: Similarly to the fixed-parameter algorithm we use a bicriteria approach to reduce the treewidth of the input graphs to a function of the considered parameters – and, more importantly, the treewidth of a derived auxiliary graph that arises from the disjoint union of all $G_i$ by identifying vertices in the intersections (both edges and vertices) of consecutive $G_i$ with one another. For Result 3 this needs to be preceded by a careful reduction of $t$ to a function of $k$ using Result 2. Once we are in a situation of bounded treewidth, we want to invoke Courcelle’s theorem on a bounded-length MSO-formula that encodes the fact that the considered auxiliary graph has a drawing with at most $k$-crossings. However, previously no such formula was known. To overcome this difficulty, we formulate a result of independent interest:

• $\mathrm{■}$

  We give an $f(k)$-length MSO-formula for expressing the existence of a drawing of a connected graph $G$ with at most $k$ crossings on a graph derived in polynomial time from $G$ in a way that crossings and rotations around cut vertices of P-nodes and high-degree cut vertices are given by the interpretation of the free variables.

The crucial advantage over the known formulations for expressing the existence of a drawing of a connected graph $G$ with at most $k$ crossings via excluding Kuratowski minors after identifying crossings (which is also used in the known $\mathrm{𝖥𝖯𝖳}$-algorithm for Crossing Number) is that the known formulations give us no direct knowledge of the drawing. Let us highlight the fact that the graph derived from $G$ has treewidth bounded in $\mathrm{tw}(G)+r$, which is where $r$ comes in as a parameter in Result 4.

The first problems considered by this working group are Upward and Rectilinear Planarity Testing. Given a directed acyclic graph $G$, upward planarity testing asks whether $G$ admits a crossing-free drawing where all edges are monotonically increasing in a common direction, which is conventionally called the upward direction; see Fig.3. For an undirected graph $G$, rectilinear planarity testing asks whether $G$ admits a crossing-free drawing such that each edge is either a horizontal or a vertical segment; see Fig.3. Both upward planarity and rectilinear planarity testing are classical and extensively investigated topics in graph drawing (see, e.g. [1, 19, 15, 18]). It is known that they are both NP-complete in the so-called variable embedding setting, that is when the testing algorithm must verify whether the input graph has a combinatorial structure of its faces which allows the balancing of angles described above. Again unsurprisingly, both proofs of $\mathrm{𝖭𝖯}$-completeness follow the same logic based on a reduction from a common flow problem on planar graphs [20]. These $\mathrm{𝖭𝖯}$-completeness results have motivated a flourishing literature describing both polynomial-time solutions for special classes of graphs and parameterized solutions for general graphs. For example, polynomial-time solutions are known for both problems when the input graph has treewidth at most two [10, 12, 13, 6, 11]; also, rectilinear planarity testing can be solved in linear time if the maximum degree of the input graph is at most three [14], and upward planarity testing can be solved in linear time if the digraph has only one source vertex [2, 4, 21]. Concerning parameterized solutions, upward planarity testing is fixed-parameter tractable when parameterized by the number of triconnected components [5], by the treedepth [7], and by the number of sources [7].