A Unified FPT Framework for Crossing Number Problems

There is currently a surge of crossing number variants. A motivation for such variations is that, in practical drawing applications, not every crossing or crossing pattern of edges may be “equal” to other ones. One may, e.g., want to avoid mutual crossings of important edges. Or, to allow crossings only within specific parts of a graph, and not between unrelated parts. Or, to exclude crossings of edges of some type. Or, to allow only certain “comprehensible” crossing patterns in order to help visualize the graph. This is the main focus of the recent research direction called “beyond planarity” [15].

Paraphrasing Schaefer [45, Chapter 2], a crossing number variant minimizes, over all allowed drawings $D$ of an input graph $G$ in some specified host surface, an objective function related to the crossings in $D$. The allowed drawings may, e.g., restrict the crossings on one edge or in a local pattern of crossing edges, or prescribe or forbid certain local properties of the drawing (also depending on types or colors of edges). The host surface is usually the plane, but can be any fixed surface, orientable or not. The objective function is often the number of crossings between edges, but other possibilities include, e.g., the number of edges involved in crossings, or the number of pairs of edges that cross an odd number of times.

One usually considers the decision version of the (traditional) crossing number problem: Given an input graph $G$ of size $n$, and an integer $r$, does $G$ have a crossing number at most $r$? This problem is already $\mathrm{𝖭𝖯}$-hard in the plane, as proved by Garey and Johnson in 1983 [18], and even in very specific cases [24, 26, 8]. Moreover, the problem is $\mathrm{𝖠𝖯𝖷}$-hard [7], and the best known polynomial-time approximation algorithm [10] gives an approximation factor that is subpolynomial in $n$ only for bounded-degree graphs.

Thus, the main current focus is on algorithms that are fixed-parameter tractable ($\mathrm{𝖥𝖯𝖳}$) in $r$ – the runtime has the form $f(r)\cdot \mathrm{𝗉𝗈𝗅𝗒}(n)$, where $f$ is a computable function of the parameter $r$. For fixed $r$, Grohe [20] has described an $O(n^2)$-time algorithm, and Kawarabayashi and Reed [32] have announced an $O(n)$-time algorithm. Both rely on Courcelle’s metatheorem [14], which automatically entails a huge dependence in the parameter $r$.

Two recent approaches avoid resorting to Courcelle’s theorem. First, Colin de Verdière, Magnard, and Mohar [13] have studied the problem of embedding a graph in a two-dimensional simplicial complex (2-complex for short), a topological space obtained from a surface by adding isolated edges and identifying vertices. Among other motivations for this problem, they observe [13, Introduction] that the crossing number problem reduces to the embeddability of the input graph in a certain 2-complex depending only on $r$. Then Colin de Verdière and Magnard [12] have shown that the embeddability of a graph of size $n$ in a 2-complex of size $C$ can be tested in $2^{\mathrm{𝗉𝗈𝗅𝗒}(C)}\cdot n^2$ time. Hence, this results in a $2^{\mathrm{𝗉𝗈𝗅𝗒}(r)}\cdot n^2$-time algorithm for the crossing number problem, which, moreover, extends to any fixed surface.

Second, even more recently, Lokshtanov, Panolan, Saurabh, Sharma, Xue, and Zehavi [35] have given a $2^{𝒪(r\log r)}\cdot n$-time algorithm for the traditional crossing number problem in the plane, by a reduction to bounded treewidth and dynamic programming, all in time linear in $n$.

For other flavors of crossing numbers, which are (typically) also $\mathrm{𝖭𝖯}$-hard, the literature on FPT algorithms is scarce; besides Pelsmajer, Schaefer, and Štefankovič [41] giving $\mathrm{𝖥𝖯𝖳}$ algorithms for the odd and pair crossing numbers, we are only aware of two very recent papers, which bring a general approach to multiple crossing number flavors and which we now detail. (The various flavors of crossing numbers are defined in Section 5.)

First, Münch and Rutter [37], extending Grohe’s approach [20], provide a framework for quadratic $\mathrm{𝖥𝖯𝖳}$ algorithms for the crossing number of several types of beyond-planar drawings of graphs in the plane, characterized by forbidden combinatorial crossing patterns. This includes the crossing number of $k$-planar, $k$-quasi-planar, min-$k$-planar, fan-crossing, and fan-crossing free drawings of a graph for any constant $k$.

Second, Hamm, Klute, and Parada [22], in a very recent preprint, have announced a generalization of the previous framework [37], also handling forbidden topological crossing patterns in drawing types in the plane and, more importantly, bringing the possibility of handling predrawn parts of the input graph (as already known for the traditional crossing number [21]). The dependence in the size $n$ of the input graph is an unspecified polynomial.

The above results all rely on Courcelle’s theorem. Apart from that, we are only aware of sporadic results for isolated variants. Kawarabayashi and Reed [32] and Jansen, Lokshtanov, and Saurabh [30] both claim, without details, a linear $\mathrm{𝖥𝖯𝖳}$ algorithm to compute the skewness of a graph, and Nöllenburg et al. [39] give a non-uniform $\mathrm{𝖥𝖯𝖳}$ algorithm for the splitting number in surfaces. All mentioned papers except Nöllenburg et al. are restricted to the plane.

Our general framework takes the following form. We fix a surface $𝒮$ and an objective function $\kappa$ from the set $𝒟$ of (possibly edge-colored) topological drawings of graphs on $𝒮$ to the set ${\mathbb{Z}}_{+}\cup \{\mathrm{\infty }\}$; the allowed drawings $D$ are those that satisfy . The map $\kappa$ has to satisfy some natural monotonicity conditions, defined later. Given an integer $r$, we prove that deciding whether an input graph $G$ has a drawing $D$ on $𝒮$ with $\kappa (D)\le r$ can be done in quadratic time in the size $n$ of $G$, and exponential in a polynomial of the other parameters, namely the genus of $𝒮$, the maximum size of a “fully crossing” drawing $D^{\times }$ satisfying $\kappa (D^{\times })\le r$, and the integer $r$. This remains true if one allows a bounded number of (possibly color-restricted) edge removals and vertex splits to $G$ before drawing it; these numbers are also parameters. The proof is a reduction to the already mentioned problem of deciding the embeddability of a graph on a 2-complex [12]; while the general strategy is intuitive, many subtle technical details need to be overcome to make it all work.

We deduce $\mathrm{𝖥𝖯𝖳}$ algorithms with runtime quadratic in the size $n$ of the input graph, and exponential in a polynomial of the other parameters, for many established crossing number variants; we now survey some of them. First, we can restrict ourselves to many established drawing styles, such as $k$-planar, $k$-quasi-planar, min-$k$-planar, fan-crossing, weakly and strongly fan-planar, $k$-gap, and fixed-rotation drawings ($k$ being an additional fixed parameter). For the $k$-gap and fixed rotation cases, no $\mathrm{𝖥𝖯𝖳}$ algorithms were known. Second, we may assign colors to the edges of the input graph and count the crossings differently depending on the colors of the edges involved, leading to the first $\mathrm{𝖥𝖯𝖳}$ algorithms on the joint crossing number on surfaces and its generalizations. Third, assuming suitable additional properties, we can handle problems that do not count the crossings, but rather the number of edges, or pairs of edges, involved in crossings, such as the edge, pair, and odd crossing numbers (no $\mathrm{𝖥𝖯𝖳}$ algorithm was known for the edge crossing number). And fourth, since we allow for prior edge removals and vertex splits, our framework encompasses, e.g., the skewness, for which $\mathrm{𝖥𝖯𝖳}$ algorithms were only sketched [32, 30] in the plane, and the splitting number, which was only known to admit a nonuniform $\mathrm{𝖥𝖯𝖳}$ algorithm [39].

Last but not least, all these four aspects that define flavors of crossing numbers can be combined arbitrarily, and our main results are valid not only in the plane, but for arbitrary surfaces. For most flavors of crossing number, the arguments are direct, though they really differ according to the flavor; they essentially boil down to checking some technical conditions (see Definition 3.1), and to giving an algorithm (not necessarily polynomial) to check a given drawing of bounded size and to count its crossings (see Theorem 3.2). However, for a couple of crossing number flavors (in particular, when fixing the rotation scheme), additional ingredients are needed.

Our main contribution is a convenient, versatile, and unified framework capturing a very general class of crossing number variants while giving $\mathrm{𝖥𝖯𝖳}$ algorithms. In particular, as listed above, we get new $\mathrm{𝖥𝖯𝖳}$ results for several established variants and their generalizations (to surfaces, or by combining the features of multiple variants). It is conceivable that some of the variants newly covered by our framework could be proved $\mathrm{𝖥𝖯𝖳}$ using other techniques, perhaps the (very powerful) metatheorem of Courcelle, as already used in [20, 21, 37, 22]. However, such developments are extremely delicate even in isolated variants and lead to hard-to-describe algorithms. Indeed, first, checking a given drawing and counting its crossings must be formalized in the MSO₂ logic of graphs, which usually needs heavy tricks tailored to the specific case; second, there remains the specific and often highly nontrivial treewidth reduction step to be done. So far, such approaches have been successful only in the case of the plane.

Moreover, all approaches using Courcelle’s theorem inherently come with a high computational cost. Indeed, they result in algorithms with a huge multi-level exponential dependence in the parameter $r$; for instance, it is an exponential tower of height at least four in the case of [20] and three in the case of [32], see the discussion in [35]. In contrast, our algorithms are singly exponential in a polynomial in $r$. Also, while Courcelle’s theorem itself runs in linear time in the size $n$ of the input graph, the necessary treewidth reduction step requires quadratic time, if not more, in the known approaches for the non-traditional crossing numbers. Our algorithms have a quadratic dependence in $n$, and the only bottleneck to a linear-time dependence is the quadratic runtime of the current best embeddability algorithm [12].

The frameworks used in the two very recent works mentioned above [37, 22], which both use treewidth reduction and Courcelle’s theorem, can handle some of the drawing styles that we encompass, but different counting functions, edge removals and vertex splits, and nonplanar surfaces are out of their reach. However, it should not be difficult to extend their framework to handle edge-colored graphs, thanks to the MSO₂ logic being able to handle arbitrary sets of edges. On the other hand, the recent breakthrough of Lokshtanov et al. [35] for the traditional crossing number problem may fuel hope for more $2^{𝒪(r\log r)}\cdot n$-time algorithms, but tweaking all ingredients of that highly technical paper seems hard, even for isolated crossing number variants, and moreover this approach is inapplicable to surfaces other than the plane, due to the use of several inherently planar techniques (3-connectivity arguments and dependence on [30]).

After the preliminaries (Section 2), we describe our general framework and state our main result (Section 3), which is then proved (Section 4). We then list the numerous applications to crossing number variants (Section 5).

In this paper, graphs are finite and undirected, but not necessarily simple unless specifically noted. The size of a graph $G$ is the number of vertices plus the number of edges of $G$. A vertex split of a graph $G$ at vertex $v$ creates a new vertex $v^{\prime }$ and replaces some of the edges incident to $v$ by making them incident to $v^{\prime }$ instead of $v$.

We follow [2, 36] for surface topology. A surface $𝒮$ is a topological space obtained from finitely many disjoint solid, two-dimensional triangles by identifying some of their edges in pairs. Surfaces are not necessarily connected. The boundary of $𝒮$ is the closure of the union of the unidentified edges. The (Euler) genus of a connected surface is twice its number of “handles”, if it is orientable, and is its number of “crosscaps”, otherwise. The topological size of $𝒮$ equals $s:=d+b+g$, where $d$ is the number of connected components of $𝒮$, $g$ is the sum of the (Euler) genera of its connected components, and $b$ is the number of boundary components. The plane is not a surface according to our definition, but in this paper it can always be substituted with a disk, which is (homeomorphic to) a surface. A self-homeomorphism of $𝒮$ is just a homeomorphism from $𝒮$ to $𝒮$.

A curve $c$ in a topological space $𝒳$ is a continuous map from the closed interval $[0,1]$ into $𝒳$. The relative interior of $c$ is the image, under $c$, of the open interval $(0,1)$. In a drawing $D$ of a graph $G$ in a topological space $𝒳$, vertices are represented by points of $𝒳$ and edges by curves in $𝒳$ such that the endpoints $c(0)$ and $c(1)$ of a curve $c$ are the images of the end vertices of the corresponding edge. Moreover, we assume that distinct vertices are mapped to distinct points and that the relative interiors of the edges avoid the images of the vertices. Given a point $x\in 𝒳$, its multiplicity in $D$ is the number of pairs $(c,t)$ such that $c(t)=x$, where $c$ is a curve representing an edge of $G$ in $D$, and $t\in (0,1)$. An intersection point (shortly an intersection) of $D$ is a point with multiplicity at least two. We only consider drawings $D$ with finitely many intersection points.

When considering a drawing $D$ of a graph $G$ on a surface $𝒮$, we always implicitly assume that $G$ has no isolated vertex and that the image of $D$ avoids the boundary of $𝒮$; these conditions are actually benign in a graph drawing context. In $D$, each edge $e$ is subdivided into (finitely many) pieces by the intersection points along $e$. A point of multiplicity two corresponds to a crossing if no local perturbation of the curves can remove this intersection, or to a tangency, otherwise. $D$ is normal [44] if every intersection point has multiplicity two and is a crossing (not a tangency). Moreover, $D$ is simple if it is normal, no edge self-crosses, no two adjacent edges cross, and no two edges cross more than once.¹¹1Note that many authors do not consider a drawing $D$ simple if $D$ contains two parallel edges (even uncrossed), as two parallel edges necessarily intersect at their two endpoints. Likewise, uncrossed loops are usually not allowed in simple drawings. We do not make these additional restrictions here for technical reasons connected to Definition 3.1; see also Proposition 5.2.

The (traditional) crossing number of a graph $G$ in a surface $𝒮$ is the least number of crossings over all normal drawings of $G$ in $𝒮$. Many variations exist [45], see Section 5.

We need to represent drawings of graphs on a surface $𝒮$ combinatorially, up to self-homeomorphisms of $𝒮$. Cellular embeddings can be represented by combinatorial maps [16], but we need to allow crossings, and moreover faces need not be disks. We can achieve this, ultimately relying on combinatorial maps. Details can be found in the full version.

In this paper, a $2$-complex $𝒞$ (or two-dimensional simplicial complex) is a topological space obtained from a simple graph (without loops or multiple edges) by attaching solid, two-dimensional triangles to some of its cycles of length three; see Figure 1.²²2Our definition of 2-complex slightly departs from the standard one; it is the same as a geometric simplicial complex of dimension at most two, realized in some ambient space of dimension large enough. The simplices of $𝒞$ are its vertices, edges, and triangles. We can easily represent 2-complexes algorithmically, by storing the vertices, edges, and triangles, and the incidences between them. In general, many such representations correspond to the same topological space, and the choice of the representation only impacts the complexity analysis of our algorithms. The class of 2-complexes is quite general; it contains all graphs, all surfaces, and any space obtained from a surface by identifying finitely many finite subsets of points and by adding finitely many edges between any two points.

An isolated edge of a 2-complex $𝒞$ is an edge incident to no triangle. The surface part of $𝒞$ is the union of all its triangles, together with their incident vertices and edges. A singular point of $𝒞$ is a point that has no open neighborhood homeomorphic to an open disk, a closed half-disk, or an open segment.

Our above definition of drawings in topological spaces applies to drawings in 2-complexes. In particular, vertices of $G$ may lie anywhere on $𝒞$, and edges of $G$ as curves may traverse several vertices, edges, and triangles of $𝒞$. An embedding of $G$ into $𝒞$ is a drawing without any intersection point.

The embeddability problem takes as input a graph $G$ and a 2-complex $𝒞$, and the task is to decide whether $G$ has an embedding in $𝒞$. This problem is fixed-parameter tractable in the size of the input 2-complex:

We apply our framework with a single color ($c=1$), no vertex splits or edge removals ($p=q_1=0$), and in the case where $𝒟$ is the set of drawings of graphs on $𝒮$. For any drawing $D$, let $\kappa (D)$ be the number of crossings in $D$, or $\mathrm{\infty }$ if $D$ is not a normal drawing. Moreover, let $\lambda (i)=4i$. Since only if $D$ is normal, $(\kappa ,\lambda )$ is a crossing-counting pair. Theorem 3.2 implies the result. $◀$

We now turn to the promised applications. We survey, in order, specific drawing styles, colored crossing number problems, various counting methods, and problems where prior edge removals and vertex splits are allowed. Throughout this section, again, let $𝒮$ be a surface and $𝒟$ the set of colored drawings of graphs on $𝒮$. In our reductions to the $(\kappa ,\lambda )$-Crossing Number problem, we always set $p=q_1=\mathrm{\dots }=q_c=0$ except in Section 5.4. In nearly all cases, only normal drawings of graphs are considered. Note that in all cases, for positive instances, we can compute a corresponding drawing; see the full version. Statements marked with * are proved in the full version.

Theorem 3.2 allows for almost endless combinations for crossing number variants, in terms of drawing styles, ways to count crossings, allowed vertex splits and edge removals, all possibly taking edge colors into account, all on an arbitrary surface.

Nonetheless, in our definition of crossing-counting pair, $\kappa (D)$ must functionally bound the total number of intersection points in the drawing $D$, and the value of $\kappa$ cannot grow upon deletion of vertices and edges. The first requirement immediately excludes, e.g., the local crossing number (the minimum $r$ such that a given graph has an $r$-planar drawing, which is $\mathrm{𝖭𝖯}$-complete to compute already for $r=1$ [8, 19]), and the second requirement excludes some recently introduced drawing styles such as, for instance, $1^{+}$ and $2^{+}$-real face drawings [5]. It is conceivable that Courcelle-based approaches would be able to handle $1^{+}$ and $2^{+}$-real face drawings, albeit not easily.

Another weakness, in particular compared to the very recent preprint by Hamm, Klute, and Parada [22], is our quite restricted ability to handle predrawn parts of the input graph, essentially limited to fixing uncrossable parts of the graph via rigid subembeddings, and to special restrictions like the fixed rotation system in Theorem 5.6. In contrast, [21] and [22] are very general in this respect and, in particular, allow crossings of fixed parts with the unfixed rest of the graph.

Beyond their use for strongly fan-planar drawings, surfaces with boundaries can be useful for other problems, because they allow to pinpoint specific regions of the surface. One could actually consider a version with colored boundaries, restricting Item 1(d) of the definition of a crossing-counting pair to color-preserving self-homeomorphisms; all our arguments carry through. Finally, a possible extension of the $(\kappa ,\lambda )$-Crossing Number problem would be to replace the surface $𝒮$ with an arbitrary 2-complex. We leave open whether such an extension is possible, and also potential applications.