Recognizing 2-Layer and Outer $k$-Planar Graphs

When evaluating the quality of a graph drawing, one of the established metrics is the number of crossings, whose importance is supported by user experiments [42]. Unfortunately, computing the crossing number of a given graph, that is, the minimum number of crossings over all drawings of the graph, is NP-hard [27], even for graphs that become planar after removal of a single edge [14]. On the other hand, the problem is fixed-parameter tractable ($\mathrm{𝖥𝖯𝖳}$) with respect to the natural parameter, that is, the number of crossings [29, 33]. Many variants of the crossing number have been studied; see Schaefer’s survey [44]. Two variants with geometric restrictions have attracted considerable attention: 2-layer crossing minimization and circular (or convex, or 1-page) crossing minimization, where the placement of the vertices is restricted to two parallel lines (called layers) and to a circle, respectively. In both cases, edges are drawn as straight-line segments. Circular crossing minimization is $\mathrm{𝖭𝖯}$-hard, but admits $\mathrm{𝖥𝖯𝖳}$-algorithms with respect to the natural parameter [6, 34]. In practice, often the so-called sifting heuristic is used [7]. Circular crossing minimization can be seen as a special case of a book embedding problem, where vertices must lie on a straight line, the spine of the book, and each edge must be drawn on one of a given number of halfplanes called pages whose intersection is the spine. In this setting, crossing minimization is interesting even if the order of the vertices along the spine is given [8, 38].

The 2-layer variant comes in two settings: one-sided crossing minimization (OSCM) and two-sided crossing minimization (TSCM). In OSCM, the input consists of a (bipartite) graph and a linear order for the vertices on one side of the bipartition; the task is to find a linear order for the vertices on the other side that minimizes the total number of crossings. In TSCM, the linear orders on both layers can be chosen freely. OSCM is an important step in the so-called Sugiyama framework for drawing hierarchical graphs [46], that is, graphs where each vertex is assigned to a specific layer. OSCM was the topic of the Parameterized Algorithms and Computational Experiments Challenge (PACE¹¹1https://pacechallenge.org/2024/) 2024. Both OSCM and TSCM are $\mathrm{𝖭𝖯}$-hard; OSCM even for the disjoint union of 4-stars [39] and for trees [19]. On the positive side, OSCM admits a subexponential $\mathrm{𝖥𝖯𝖳}$-algorithm; it runs in $O(k{2}^{\sqrt{2k}}+n)$ time [35]. TSCM also admits an $\mathrm{𝖥𝖯𝖳}$-algorithm; it runs in $2^{O(k)}+n^{O(1)}$ time [36].

In the context of beyond-planar graphs, a local version of the crossing number has also received considerable attention [22, 18]. A graph is $k$-planar if it admits a drawing with at most $k$ crossings per edge. The local crossing number of a graph is the smallest $k$ such that the graph is $k$-planar. The recognition of 1-planar graphs has long been known to be NP-hard [28]. Later, it turned out that the recognition of $k$-planar graphs is NP-hard for every $k$ [47]. Hence, it is unlikely that $\mathrm{𝖥𝖯𝖳}$- or $\mathrm{𝖷𝖯}$-algorithms exist with respect to the natural parameter $k$. On the other hand, recognizing 1-planar graphs is fixed-parameter tractable with respect to tree-depth and cyclomatic number [5]. The problem remains $\mathrm{𝖭𝖯}$-hard, however, for graphs of bounded bandwidth (and hence, pathwidth and treewidth). The local crossing number has also been studied in the context of book embeddings [37, 1].

In this paper, we study the above-mentioned geometric restrictions, but with respect to the local crossing number. The resulting graph classes are called 2-layer $k$-planar graphs and outer $k$-planar graphs; see Figure 1.

The former were studied by Angelini, Da Lozzo, Förster, and Schneck [3]. Among others, they gave bounds on the edge density of these graphs and characterized 2-layer $k$-planar graphs with the maximum edge density for $k\in \{2,4\}$. They concluded that “the general recognition and characterization of 2-layer $k$-planar graphs remain important open problems”. According to Schaefer’s survey [44] on crossing numbers, Kainen [32] introduced the “local outerplanar crossing number”, which minimizes, over all circular drawings, the largest number of crossings along any edge. Outer $k$-planar graphs have been studied by Pach and Tóth [40], who showed that any outer $k$-planar graph with $n$ vertices has at most $4.1\sqrt{k}n$ edges. For $k\le 3$, they established a better bound $(k+3)(n-2)$, which is tight for $k\in \{1,2\}$. For $k\ge 5$, the constant factor was later improved to $\sqrt{243/40}\approx 2.46$ [2].

We study the parameterized complexity of the two recognition problems with respect to the natural parameter $k$. For $k=0$, the two classes of graphs are exactly the caterpillars and outerplanar graphs, respectively, which can be recognized in linear time. There are also linear-time algorithms for recognizing outer $1$-planar graphs [4, 30]. The authors of [30] posed the existence of polynomial-time algorithms for recognizing outer 2-planar graphs as an open problem. A partial answer has been given by Hong and Nagamochi [31], showing that full outer 2-planar graphs can be recognized in linear time. Outer $k$-planar drawings are full if no crossing appears on the boundary of the outer face. The authors of [16] generalized this result and showed that, for every integer $k$, full outer $k$-planarity is testable in $O(f(k)\cdot n)$ time, for a computable function $f$. They also showed that outer $k$-planar graphs can be recognized in quasi-polynomial time, which implies that, for every integer $k$, testing outer $k$-planarity is not $\mathrm{𝖭𝖯}$-hard unless the Exponential-Time Hypothesis fails.

Let $G$ be a graph. We let $V(G)$ and $E(G)$ denote the sets of vertices and edges of $G$, respectively. For a vertex $v$ of $G$, let $N_G(v)$ be the set of neighbors of $v$ in $G$, and let ${\delta }_G(v)$ be the set of edges incident to $v$. For $U\subseteq V(G)$, we define $N_G(U)=({\bigcup }_{v\in U}{N}_G(v))\setminus U$, $N_G[U]=N_G(U)\cup U$, and ${\delta }_G(U)={\bigcup }_{v\in U}{\delta }_G(v)$. We may omit the subscript $G$ when it is clear from the context. The subgraph of $G$ induced by $U\subseteq V(G)$ is denoted by $G[U]$. A vertex is called a leaf if it has exactly one neighbor.

We use $[\mathrm{\ell }]$ as shorthand for $\{1,2,\mathrm{\dots },\mathrm{\ell }\}$. Let $n=|V(G)|$, and let $\sigma :V(G)\to [n]$ be a linear order of the vertices of $G$ (i.e., a bijection between $V(G)$ and $[n]$). For $\{u,v\}\in E$, the stretch of edge $\{u,v\}$ in $\sigma$ is defined as $|\sigma (u)-\sigma (v)|$. The bandwidth of $\sigma$ (with respect to $G$) is the maximum stretch of an edge of $G$ in $\sigma$. The bandwidth of $G$, denoted by $\mathrm{bw}(G)$, is the minimum integer $k$ such that $G$ has a linear order $\sigma$ of $V$ with bandwidth at most $k$.

We define a circular drawing of a graph $G$ to be a cyclic order $D=(v_1,\mathrm{\dots },v_n)$ of $V(G)$. We say that an edge $\{v_i,v_j\}$ with pierces a pair of (not necessarily adjacent) vertices $\{v_{i^{\prime }},v_{j^{\prime }}\}$ with if either or holds. In particular, if $\{v_{i^{\prime }},v_{j^{\prime }}\}$ is an edge of $G$, we say that $\{v_i,v_j\}$ crosses $\{v_{i^{\prime }},v_{j^{\prime }}\}$. For an edge $e$, let ${\mathrm{cr}}_D(e)$ denote the number of edges that cross $e$ in $D$. A circular drawing $D$ is $k$-planar (or an outer $k$-planar drawing) if every edge crosses at most $k$ edges in $D$. Since whether two edges cross is determined only by the cyclic vertex order, in this paper, we allow the edges to be drawn arbitrarily.

Let $G$ be a bipartite graph with $V(G)=X\cup Y$, $X\cap Y=\mathrm{\varnothing }$, and $E(G)\subseteq X\times Y$. A 2-layer drawing of $G$ is a pair of (strict) linear orders  and  defined on $X$ and on $Y$, respectively. A crossing in $D$ is defined by a pair of edges $\{x,y\}$ and $\{x^{\prime },y^{\prime }\}$ with distinct endpoints $x,x^{\prime }\in X$ and distinct endpoints $y,y^{\prime }\in Y$ such that and . The notation ${\mathrm{cr}}_D(e)$ is defined as above. Moreover, for two distinct edges $e$ and $e^{\prime }$, let ${\mathrm{cr}}_D(e,e^{\prime })$$=1$ if $e$ crosses $e^{\prime }$; ${\mathrm{cr}}_D(e,e^{\prime })=0$ otherwise. For distinct $x,x^{\prime }\in X$, we say that $x$ is to the left of $x^{\prime }$ in $D$ if . Equivalently, we say that $x^{\prime }$ is to the right of $x$. The leftmost (resp. rightmost) of $X$ in $D$ is the smallest (resp. largest) vertex in $X$ under the linear order . We also use these notions for vertices in $Y$. For an integer $k\ge 0$, a 2-layer drawing $D$ of $G$ is said to be $k$-planar if, for each edge $e$ of $G$, ${\mathrm{cr}}_D(e)\le k$. For (not necessarily disjoint) vertex sets $A,B\subseteq X\cup Y$ and 2-layer drawings $D_A$ of $G[A]$ and $D_B$ of $G[B]$, we say that $D_A$ is compatible with $D_B$ (or equivalently $D_B$ is compatible with $D_A$) if, for every pair $\{z,z^{\prime }\}\subseteq A\cap B$ of vertices that both are in the same set of the bipartition $Z\in \{X,Y\}$, we have that in $D_A$ if and only if in $D_B$.

In this section, we design an $\mathrm{𝖥𝖯𝖳}$-algorithm for recognizing 2-layer $k$-planar graphs when the order of the vertices on one layer is given as input. The problem is defined as follows.

The algorithm in Theorem 3 exploits the prescribed order on $X$, which is not specified in the two-sided case. This difference is reflected by the parameterized complexity of the two problems. The two-sided case turns out to be XNLP-hard, meaning that it is unlikely to be fixed-parameter tractable. On the other hand, we design a polynomial-time algorithm for the two-sided case, provided that $k$ is fixed. We use this algorithm also to show that the problem is contained in XNLP. Formally, the problem is defined as follows.

In this section, we discuss the parameterized complexity of recognizing outer $k$-planar graphs.