Heuristics for Exact 1-Planarity Testing

It has been established early on in the history of Graph Drawing that the number of crossings has a major influence on the readability of drawings [37, 38, 39]. This reinforces the continued interest in the extensively studied crossing minimization problem, which asks for the minimum number of crossings over all drawings of a given graph. It was shown as early as 1983 that the problem is NP-complete [20]. Due to its foundational nature, it has fueled a large number of results that address combinatorial and algorithmic aspects of crossing numbers. We refer to the survey of Schaefer for an overview of this extensive field [44]. Due to the practical importance of the problem, these developments have early on been paralleled by more applied works that are concerned with solving the crossing minimization problem in practice. Today, there is a large amount of literature that deals with computing the crossing number either exactly in exponential time, based on formulations as integer linear programs [8, 13, 33], or heuristically in polynomial time [11, 12, 22]. Heuristics often work by efficiently and optimally inserting vertices or edges into a drawing, allowing to introduce crossings only between pairs of edges where at least one of the edges is currently being inserted; a strategy that has also proved to be successful for straight-line drawings [6, 40, 41, 42].

A more recent development is based on the hypothesis that in addition to the number of crossings, a major influence on the readability of drawings comes from the distribution of the crossings within the drawing. This has lead to the definition of so-called beyond-planar graphs that admit drawings whose crossings avoid certain patterns that are considered to impede readability. Prominent examples of beyond-planarity concepts are $k$-planarity, $k$-quasi-planarity, fan-planarity, gap-planarity, RAC-planarity, min-$k$-planarity as well as corresponding outer and upward variants; we refer to [26] for a survey. One of the most widely known beyond-planarity concepts is 1-planarity, where a graph is called 1-planar if it can be drawn in the plane such that each edge has at most one crossing. Despite the apparent simplicity, 1-planar graphs form a rich class that has spurred a substantial amount of research. From a combinatorial perspective, questions about density, coloring and structural decompositions have been deeply investigated; we refer to [27, 45] for surveys.

From an algorithmic perspective, it is well known that testing 1-planarity is NP-complete [21, 28], even for graphs of bounded bandwidth, pathwidth or treewidth [4], as well as for graphs that can be made planar by the removal of a single edge [9] or graphs with a fixed rotation system [3]. Polynomial-time recognition algorithms are only known for restricted subclasses such as outer 1-planar graphs [2, 25], maximal 1-planar graphs with a fixed rotation system [19], 1-planar maximal graphs of pathwidth $w$ [31], and optimal 1-planar graphs [7]. Recent years have seen a plethora of fixed-parameter tractability (FPT) results on testing 1-planarity. In particular, Bannister, Cabello and Eppstein [4] showed that the problem is FPT with respect to the vertex cover number, the tree-depth, and the cyclomatic number. Various recent results, see e.g. [16, 23, 24, 32], imply that 1-planarity is FPT with respect to the 1-planar crossing number, i.e., the minimum number of crossings over all 1-planar drawings of a graph. The mentioned results are however only of theoretical interest as they rely on deep theoretical results such as Courcelle’s Theorem [15] or testing embeddability of graphs in 2-complexes [17].

A key motivation that initiated the study of beyond-planarity was the observation that while many real world-graphs are non-planar, they are usually sparse and close to planarity in the sense described above, namely that they have drawings whose crossings are well-scattered [26]. Correspondingly, the problem of recognizing beyond-planar graphs and in particular testing 1-planarity has a strong practical motivation. Despite this and in stark contrast to the problem of crossing optimization, where the theoretical developments have been accompanied by corresponding practical results, there is a distinct scarcity of practical algorithms in the area of beyond-planarity. In fact, we are only aware of two attempts.

Angelini, Bekos, Kaufmann and Schneck [1] present an algorithm that is based on enumerating all topological drawings of a graph incrementally by iteratively inserting the edges. This is useful, e.g., to devise small counterexamples or to confirm conjectures on small graphs with less than 15 vertices, but it is hardly useful for practical applications. Binucci, Didimo and Montecchiani [5] present an easy-to-implement algorithm, called 1PlanarTester, for recognizing $1$-planar graphs that is based on backtracking and is quite effective for small graphs. As a graph is 1-planar if and only if all its biconnected components are 1-planar, they process the biconnected components independently. For each biconnected component, they fix a global ordering $\sigma$ on the set of all pairs of non-adjacent edges, consider each such crossing candidate pair $\{e,f\}$ in the order of $\sigma$ and branch on the binary decision of whether $e$ and $f$ should cross. This is repeated until a 1-planar drawing is found or the whole search tree has been explored and the instance is rejected. Branches that cannot lead to a solution, e.g., when an edge receives more than one crossing, or there is a non-planar subgraph whose edges may not receive further crossings, are excluded from the backtracking. The authors extend this basic algorithm by combining it with several filter criteria that exclude additional branches, e.g., based on the addition of “kite” edges around crossings and density bounds for planar and 1-planar graphs. The algorithm can handle graphs with up to 30 vertices in a reasonable amount of time. However, on graphs with up to 50 vertices the algorithm often either gives a positive answer in less than 0.2 seconds or does not give an answer within a three-hour time limit. This emphasizes the crucial role of the order $\sigma$; either a lucky guess of helpful crossings early on paves the ways towards a solution, or the algorithm more or less explores the entire search tree.

We assume familiarity with basic graph terminology. Throughout this paper, all graphs are simple, i.e., they have neither parallel edges nor loops. We use $K_n$ to denote the complete graph on $n$ vertices and $K_{n,m}$ to denote the complete bipartite graph whose bipartition contains $n$ and $m$ vertices, respectively.

A drawing $\mathrm{\Gamma }$ of a graph $G=(V,E)$ maps every vertex $v\in V$ to a point $\mathrm{\Gamma }(v)$ in the plane and every edge $uv\in E$ to a Jordan arc with endpoints $\mathrm{\Gamma }(u),\mathrm{\Gamma }(v)$ that does not pass through any $\mathrm{\Gamma }(w)$ for $w\in V\setminus \{u,v\}$. For simplicity, we identify vertices and edges with their images in a drawing. A crossing is a common interior point of two edges. A drawing $\mathrm{\Gamma }$ of a graph $G$ is 1-planar, if every edge is crossed at most once in $\mathrm{\Gamma }$. The planarization of a drawing $\mathrm{\Gamma }$ is the graph we obtain from $\mathrm{\Gamma }$ by replacing every crossing in $\mathrm{\Gamma }$ with a dummy vertex. A drawing subdivides the plane into connected regions called faces, one of which is unbounded and is called outer face. An embedding of a graph $G$ is the equivalence class of those drawings of $G$ that share the same face structure and cyclic order of the incident edges around each vertex. A $1$-planar embedding is an embedding induced by a $1$-planar drawing and a $1$-plane graph is a graph together with a fixed $1$-planar embedding. A kite is a $1$-plane graph isomorphic to $K_4$ whose outer face is bounded by a cycle of four vertices and four uncrossed edges, called kite edges, while the remaining two edges cross each other; see Figure 1.

It is well known that a 1-planar graph on $n$ vertices has at most $4n-8$ edges [35]. We call a graph with more than $4n-8$ edges trivially non-1-planar. A graph is biconnected, if it is connected and remains connected after the removal of any vertex. Recall that a graph is non-planar if and only if it contains a subgraph that is isomorphic to a subdivision of $K_{3,3}$ or $K_5$ as a subgraph [29]. We call such a subgraph a Kuratowski-subdivision.

In this section we formalize the backtracking strategy we use in the rest of this paper. It is based on a search tree similar to the one of Binucci et al. [5] described in the introduction, whose nodes correspond to partial solutions. Recall that the algorithm of Binucci et al. constructs the search tree based on a global order $\sigma$ of the crossing candidates. Thus, in their setting, a partial solution corresponds to a bitstring that describes the choices made on a prefix of the order $\sigma$. As mentioned in the introduction, the performance seems to crucially depend on $\sigma$. We conjecture that, rather than fixing a global order $\sigma$ on the crossing candidates, it may be beneficial to choose the next crossing candidate to branch on according to criteria that take into account the current partial solution and thus allow different subtrees to explore the same crossing candidate at different depths of the search tree. This may enable the search to focus on critical parts of a partial solution and has the potential to reject infeasible partial solutions more quickly. For this reason, we choose a different representation of partial solutions that encodes the current state more explicitly.

As a graph is 1-planar if and only if each of its biconnected components is 1-planar, we assume in the following that our input graph $G=(V,E)$ is biconnected. Before we describe our backtracking strategy, we introduce some useful notation. For a crossing candidate $\{e,f\}$ with $e=uv$, $f=wy$ let $G_{\{e,f\}}$ denote the graph we obtain by inserting a dummy vertex $x$ subdividing $e$ and $f$, i.e., $G_{\{e,f\}}=(V\cup \{x\},(E\setminus \{e,f\})\cup \{ux,vx,wx,yx\})$. We say that the edges $ux,vx$ and $wx,yx$ stem from $e$ and $f$, respectively. For a set $C$ of crossing candidates such that each edge in $E$ is contained in at most one pair of $C$, we denote by $G_C$ the graph we obtain from $G$ by inserting a dummy vertex as described above for every pair in $C$.

Let $\overline{E}\subseteq \left(\genfrac{}{}{0pt}{}{E}{2}\right)$ be the set containing all crossing candidates $\{e,f\}$ consisting of non-adjacent edges $e$ and $f$. We encode a partial solution for $G$ as a pair $(C,P)$ with $C,P\subseteq \overline{E}$. The intended meaning is that we have chosen the crossing candidates in $C$ and we may still choose among the crossing candidates in $P$. Since each edge may receive at most one crossing, we require that for each edge $e\in E$ that appears in a pair $\{e,f\}\in C$, the pair $\{e,f\}$ is the only pair in $P\cup C$ that contains it. We call an edge of $G_C$ free if it is contained in a pair in $P$ and we call it saturated otherwise. Observe that $G$ is 1-planar if and only if there exists a partial solution $(C,P)$ where $G_C$ is planar. A partial solution $(C,P)$ is extendible if there exists a subset $C^{\prime }\subseteq P$ such that $G_{C\cup C^{\prime }}$ is planar.

The backtracking procedure incrementally constructs a search tree $T$ starting from the partial solution $(\mathrm{\varnothing },\overline{E})$. We process a node of $T$ representing a partial solution $(C,P)$ as follows. First, if $G_C$ is planar, we return the corresponding 1-planar embedding of $G$. Second, if $G_C$ is not planar but $P=\mathrm{\varnothing }$, we backtrack, since $(C,P)$ does not extend to a 1-planar drawing. If neither of these applies, we use a branching strategy to compute a finite set $𝒞$ of child partial solutions $(C^{\prime },P^{\prime })$ with $C\subseteq C^{\prime }\subseteq C\cup P$ and $P^{\prime }⊊P$. The chosen set $𝒞$ has to be exhaustive in the sense that the partial solution $(C,P)$ is extendible if and only if the same holds for at least one child partial solution in $𝒞$.

We note that this basic framework leaves several degrees of freedom. First, the choice of the branching strategy can have a significant impact on the size of the search tree. Second, in addition to that, the order in which the nodes of $T$ are processed can have a major impact on the time it takes to find a solution. We discuss different options in Section 4.

Third, a major issue stems from the fact that for no-instances the entire tree $T$ needs to be traversed. If we identify that a certain partial solution $(C,P)$ is not extendible, its subtree contains no solution and we can immediately backtrack. Hence, a necessary criterion for extendibility of $(C,P)$ can be used to prune the search tree whenever the criterion is not satisfied. We call such a criterion a filter. An example of such filter is excluding nodes $(C,P)$ where $G_C$ is trivially non-1-planar. We propose additional filters in Section 5.

Another optimization already described by Binucci et al. [5] exploits the fact that kite edges can always be redrawn such that they do not cross any other edge. In particular, when adding a new crossing $\{e,f\}$ to the currently considered partial solution, they insert all edges connecting an endpoint of $e$ to an endpoint of $f$ that are not already present in $G$ and make all these kite edges uncrossable, which in our setting corresponds to removing from $P$ all pairs that contain such a kite edge. We note that this can be slightly strengthened by making all edges uncrossable that are contained in a path from an endpoint of $e$ to an endpoint of $f$ whose internal vertices are all of degree 2, as such paths can also always be redrawn arbitrarily closely along $e$ and $f$ without any crossings; see Figure 2. The described optimizations help in keeping the search tree small as the number of crossings that have to be considered decreases, and violations of necessary conditions on the extendability to a 1-planar embedding are found earlier during the execution. We thus include them in each of our algorithms.

In this section, we propose different branching strategies for choosing the children of a partial solution $(C,P)$ and discuss different options for the traversal of the resulting search tree. We discuss branching strategies in Section 4.1 and traversal strategies in Section 4.2.

In this section, we describe several filters to determine that a partial solution $(C,P)$ is not extendible and, therefore, allows us to ignore its entire subtree. This has significant potential to speed up the solution speed for both 1-planar and non-1-planar instances.

We first describe the filters that were already used by Binucci et al. [5] and that we employ in all our strategies. We phrase each of them as a necessary condition, whose violation allows to cut the corresponding subtree. The first, called Planar Structure, requires that the subgraph of $G_C$ induced by the saturated edges is planar. To strengthen this, we also include the kite edges and the extended kite edges as described at the end of Section 3. The filter Edge Density rejects instances where $G_C$ is trivially non-1-planar after adding potentially missing kite edges. We propose three further types of filters.

In this section, we experimentally evaluate our backtracking procedure. A concrete instance of our backtracking procedure, called a configuration is obtained by choosing a branching strategy and a traversal strategy from Section 4 along with a subset of the filters from Section 5. As some of the strategies have additional parameters, this yields a relatively large number of possible configurations. To address this, we first perform preliminary experiments on a smaller test set and with a short time limit to assess the impact of the individual strategies and filter criteria and to ultimately determine the configuration with the best performance. Afterwards, we compare the performance of this winning configuration with that of the algorithm 1PlanarTester of Binucci et al. [5] by running it on an extensive test set in a way that closely mimics their experimental setup. As an additional reference point, we also implemented a simple ILP-based algorithm that builds on the ILP formulation of Buchheim et al. [8] for the Exact Crossing Number Problem.

In the following, we first describe the ILP formulation followed by a description of our test data and the experimental setup. Finally we report the results of our evaluation.

We proposed a new backtracking framework for exact 1-planarity testing and investigated the impact of different branching strategies, filter criteria, and traversal strategies on its effectiveness. Our experiments show that some of our optimizations massively decrease the search space for such algorithms and thus greatly enhance their performance. In particular, using Kuratowski subdivisions to guide the search more than doubles the number of solved instances compared to the baseline that uses binary branching and our best filter, SC, rejects around $90\%$ of the nodes in the search tree it is invoked on; it thus offers a significant, exponential decrease of the search space. Our best configuration combines this with threads that allow to search multiple parts of the search tree in parallel and altogether yields a practical 1-planarity testing and embedding algorithm that significantly outperforms its competitor 1PlanarTester [5] and solves most instances from our test set with up to $50$ vertices within seconds.