A Greedy Heuristic for Crossing-Angle Maximization

The crossing angle \({{\mathrm{cr\text {-}\alpha }}}(\varGamma )\) of a straight-line drawing \(\varGamma \) is defined to be the minimum over all angles created by two crossing edges in \(\varGamma \). The 24th edition of the annual Graph Drawing Challenge, held during the Graph Drawing Symposium, posed the following problem: Given a graph G, compute a straight-line drawing \(\varGamma \) on an integer grid that has a large crossing angle. In this paper we present a greedy heuristic that starts with a carefully chosen initial drawing and repeatedly moves a vertex v to a random point p if this increases the crossing angle of \(\varGamma \). This heuristic was the winning algorithm of the GD Challenge’17 [6].

Related Works. A drawing of a graph is called RAC if its minimum crossing angle is \(90^\circ \). Deciding whether a graph has a straight-line RAC drawing is an \(\mathcal {NP} \)-hard problem [1]. Giacomo et al. [13] proved that every straight-line drawing of a complete graph with at least 12 vertices has a crossing angle of \(\varTheta (\pi / n)\). Didimo et al. [7] have shown that every n-vertex graph that admits a straight-line RAC drawing has at most \(4n-10\) edges. This bound is tight, since there is an infinite family of graphs with \(4n-10\) edges that have straight-line RAC drawings. Moreover they proved that every graph has a RAC drawing with three bends per edge. Arikishu et al. [3] showed that any n-vertex graph that admits a RAC drawing with one bend or two bends per edge has at most 6.5n and 74.2n edges, respectively. For an overview over further results on RAC drawings we refer to [8]. Dujmović et al. [9] introduced the concept of \(\alpha \)AC graphs. A graph is \(\alpha \)AC if it admits a drawing with crossing angle of at least \(\alpha \). For \(\alpha > \pi /3\), \(\alpha \)AC graphs are quasiplanar graphs, i.e., graphs that admit a drawing without three mutually crossing edges, and thus have at most \(6.5n - 20\) edges. Moreover, every n-vertex \(\alpha \)AC graph with \(\alpha \in (0, \pi /2)\) has at most \((\pi / \alpha ) (3n - 6)\) edges. Besides the theoretical work on this topic, there are a few force-directed approaches that optimize the crossing angle in drawings of arbitrary graphs [2, 14], see Sect. 2.1.

Contribution. We introduce a heuristic to increase the crossing angle in a given straight-line drawing \(\varGamma \) (Sect. 3). The heuristic is accompanied by a speed-up technique to compute the pair of crossing edges in \(\varGamma \) that create the smallest crossing angle. In Sect. 4 we give an extensive evaluation of our heuristic. The evaluation is driven by three main research questions: (i) What is a good parametrization of our heuristic? (ii) Does our heuristic improve the crossing angle of a given initial drawing? (iii) What is a good choice for an initial drawing?

Let \(\varGamma \) be a straight-line drawing of a graph \(G=(V,E)\). Denote by n and m the number of vertices and edges of G, respectively. Let e and \(e'\) be two distinct edges of G. If e and \(e'\) have an interior intersection in \(\varGamma \), the function \({{\mathrm{cr\text {-}\alpha }}}(\varGamma , e, e')\) denotes the smallest angle formed by e and \(e'\) in \(\varGamma \). In case that e and \(e'\) do not intersect, we define \({{\mathrm{cr\text {-}\alpha }}}(\varGamma , e, e')\) to be \(\pi /2\). The local crossing angle of a vertex v is defined as the minimum angle of the edges incident to v, i.e., \({{{\mathrm{cr\text {-}\alpha }}}}(\varGamma , v) = \min _{e, uv \in E, e \not = uv} {{\mathrm{cr\text {-}\alpha }}}(\varGamma , e, uv)\). The crossing angle of a drawing \(\varGamma \) is defined as \({{\mathrm{cr\text {-}\alpha }}}(\varGamma ) = \min _{e, e' \in E, e\not =e' } {{\mathrm{cr\text {-}\alpha }}}(\varGamma , e, e')\). Let \(\varDelta x\) and \(\varDelta y\) be the difference of the x-coordinates and the y-coordinates of the endpoints of e in a drawing \(\varGamma \). The slope of e is the angle between e and the x-axis, i.e. \({{\mathrm{slope}}}(\varGamma , e) = \arctan (\varDelta y / \varDelta x)\) if \(\varDelta x \ne 0\) and \({{\mathrm{slope}}}(\varGamma , e) = -\pi /2\) otherwise.

Sketches of the force (a) \(F_\mathrm {cos}(v)\), (b) \(F_\mathrm {cage}(v)\) and (c) \(F_\mathrm {ang}(v)\).

Full size image

2.1 Force-Directed Approaches

In general, force-directed algorithms [10, 11] compute for each vertex v of a graph \(G=(V, E)\) a force \(F_v\). A new drawing \(\varGamma '\) is obtained from a drawing \(\varGamma \) by displacing every vertex v according to the force \(F_v\). Classically, the force \(F_v\) is a linear combination of repelling and attracting forces, i.e., all pairs of vertices repel each other, and incident vertices attract each other. It is easy to integrate new forces into this generic system, e.g., in order to increase the crossing angle. For this purpose, Huang et al. [14] introduced the cosine force \(F_{\cos }\). The force-directed approach considered by Argyriou et al. [2] uses two forces, \(F_{\mathrm {cage}}\) and \(F_{\mathrm {ang}}\), to increase the crossing angle. In the following we will describe each force.

Let \(\overrightarrow{xy}\) denote the unit length vector from x to y. Let uv, xy be two crossing edges in \(\varGamma \) and let \(\alpha \) be the angle as depicted in Fig. 1(a) and let p denote the intersection point of uv and xy, see Fig. 1. The cosine force for v is defined as \(F_{\cos }(v) = k_{\cos } \cdot \cos \alpha \cdot \overrightarrow{yx}\), where \(k_{\cos }\) is a positive constant.

The force \(F_\mathrm {cage}(v)\) is a compound of two forces \(F_\mathrm {cage}(v, x)\) and \( F_\mathrm {cage}(v, y)\). Let \(l_{ab}\) denote the distance between two points a and b. Let \(l^\star _{vx}\) be the length of the edge vx in a triangle vxp with side length \(l_{vp}\) and \(l_{xp}\), and a right angle at the point p. Then, \(F_{\mathrm {cage}}(v, x) = k_\mathrm {cage} \cdot \log ( l_{vx} / l^\star _{vx}) \overrightarrow{vx}\), where \(k_\mathrm {cage}\) is positive constant. The force \(F_{\mathrm {cage}}(v,y)\) is defined symmetrically.

Again the force \(F_\mathrm {ang}(v)\) is a compound of the forces \(F_\mathrm {ang}(v, x)\) and \(F_\mathrm {ang}(v, y)\). Consider the unit vector a that is perpendicular to the bisector of \(\overrightarrow{uv} \) and \(\overrightarrow{yx}\), refer Fig. 1c. Further, let \(\alpha '\) be the angle between the \(\overrightarrow{uv}\) and \(\overrightarrow{yx}\). Then the force \(F_\mathrm {ang}(v, x)\) is defined as \(k_\mathrm {ang} \cdot \mathrm {sign}(\alpha ' - \pi / 2) \cdot | \pi / 2 - \alpha '| / \alpha ' \cdot a\) where \(k_\mathrm {ang}\) is a positive constant. The force \(F_\mathrm {ang}(v, y)\) is defined correspondingly.

Our algorithm starts with a drawing \(\varGamma \) of a graph G and iteratively improves the crossing angle of \(\varGamma \) by moving a vertex to a better position, i.e., we locally optimize the crossing angle of the drawing; for pseudocode refer to Algorithm 1. For this purpose we greedily select a vertex v with a minimal crossing angle \({{\mathrm{cr\text {-}\alpha }}}(\varGamma , v)\). More precisely, let e and \(e'\) be two edges with a minimal crossing angle in \(\varGamma \). We set v randomly to be an endpoint of e and \(e'\). We iteratively improve the crossing angle of v by sampling a set S of T points within a square R and by moving v to the position \(p \in S\) that induces a maximal local crossing angle. We repeat this process \(L \in \mathbb {N} ^+\) times and decrease the size of R in each iteration.

More formally, denote by \(\varGamma \left[ v \mapsto p\right] \) the drawing obtained from \(\varGamma \) by moving v to the point \(p=(p_x,p_y) \in \mathbb {R} ^2\). Let \(R^i(p) = [p_x - s \cdot b^i / 2, p_y - s \cdot b^i/2] \times [p_x + s/2, p_y + s \cdot b^i / 2] \subset \mathbb {R} ^2\) be a square centered at the point p with a scaling factor \(b \in (0, 1)\) and initial side length \(s > 0\). Let \(p^0\) be the position of v in \(\varGamma \) and let \(S^0 \subset R^0(p^0)\) be a set of T points in \(R^0(p^0)\) chosen uniformly at random. Let \(p^i\) be a point in \(S^{i-1} \cup \{p^{i-1}\}\) that maximizes \({{\mathrm{cr\text {-}\alpha }}}(\varGamma \left[ v \mapsto p^i\right] , v)\). We obtain a new sample \(S^i\) by randomly selecting T points within the square \(R^i(p^i)\). Since \({{\mathrm{cr\text {-}\alpha }}}(\varGamma \left[ v \mapsto p^i\right] , v) = \max _{uv \in E, e \in E \setminus \{uv\}} {{\mathrm{cr\text {-}\alpha }}}(\varGamma \left[ v \mapsto p^i\right] , uv, e)\), the function can be evaluated in \(O(\deg (v) |E|)\) time.

3.1 Fast Minimum Angle Computation

The running time of the random sampling approach relies on computing in each iteration a pair of edges creating the minimum crossing angle \({{\mathrm{cr\text {-}\alpha }}}(\varGamma )\). More formally, we are looking for a pair of distinct edges \(e, f \in E\) that have a minimal crossing angle in a straight-line drawing \(\varGamma \), i.e., \({{\mathrm{cr\text {-}\alpha }}}(\varGamma , e, f) = {{\mathrm{cr\text {-}\alpha }}}(\varGamma )\). The well known sweep-line algorithm [4] requires \(O( (n+k) \log (n + k))\) time to report all k intersecting edges in \(\varGamma \). In general the number of intersecting edges can be \(\varOmega (m^2)\), but we are only interested in a single pair that forms the minimal crossing angle. Therefore, we propose an algorithm, which uses the slopes of the edges in \(\varGamma \) to rule out pairs of edges, which cannot form the minimum angle.

Assume that we already found two intersecting edges forming a small angle of size \(\delta > 0\). We set \(t := \left\lfloor \pi / \delta \right\rfloor \) and distribute the edges into t buckets \(B_0, \ldots , B_{t-1}\) such that bucket \(B_i\) contains exactly the edges e with \(i\pi /t \le {{\mathrm{slope}}}(\varGamma , e) + \pi /2 < (i+1)\pi /t\). Then each bucket covers an interval of size \(\pi / \left\lfloor \pi / \delta \right\rfloor \ge \delta \). Thus, if there exist edges e, f with \({{\mathrm{cr\text {-}\alpha }}}(\varGamma , e, f) < \delta \), they belong to the same or to the adjacent buckets (modulo t). Overall, we consider all pairs of edges in \(B_i \cup B_{i+1\ (\mathrm {mod}\ t)}\), \(i=1,\dots t\), and find the pair forming the smallest crossing angle. To find this pair we could apply a sweep-line algorithm to the set \(B_i \cup B_{i+1}\). In general this set can contain \(\varOmega (m)\) edges. Thus, in worst case we would not gain a speed up in comparison to a sweep-line algorithm applied to \(\varGamma \). On the other hand, in practice we expect the number of edges in a bucket to be small. If we assume this number to be a constant, the overall running time of the exhaustive check is linear in m and does not depend on the number of crossings.

Implementation Details. In the case that the slopes in \(\varGamma \) are uniformly distributed, we expect the number of edges in a bucket to decrease with an decreasing estimate \(\delta \). We set the value \(\delta \) to be the minimal crossing angle of the r longest edges in \(\varGamma \). In our implementation we set r to be 50 if the graph contains at most 5000 edges, otherwise it is 300.

The Random Sampling heuristic has several parameters which allow for many different configurations. In Sect. 4.4, we investigate the influence of the configuration on the crossing angle of the drawing computed by the random sampling approach. We investigate the question of whether the Random Sampling approach improves the crossing angle of a given drawing. Our evaluation in Sect. 4.5 answers the question affirmatively. Moreover, we expect that the crossing angle of the drawing computed by the random sampling approach depends on the choice of the initial drawing. We show that this is indeed the case (Sect. 4.6). We close the evaluation with a short running time analysis in Sect. 4.7. Our evaluation is based on a selection of artificial and real world graphs (Sect. 4.1), several choices of the initial drawing, see Sect. 4.2, and a specific way to compare two drawing algorithms (Sect. 4.3).

Setup. All experiments were conducted on a single core of an AMD Opteron Processor 6172 clocked at 2.1 GHz. The server is equipped with 256 GB RAM. All algorithms were compiled with g++-4.8.5 with optimization mode -O3.

The distribution of the sum of number of vertices and edges per graph class. The plot is scaled such that a bar of full height would contain 40 graphs.

Full size image

4.1 Benchmark Graphs

We evaluate the heuristic on the following graph classes, either purely synthetic or with a structure resembling real-world data. Figure 2 shows the size distribution of these graphs. The color of each class is used consistently throughout the paper.

Real World. The classes Rome and North (AT&T)^{Footnote 1} are the non-planar subsets of the corresponding well known benchmark sets, respectively. From each graph class we picked 100 graphs uniformly at random. The Community graphs are generated with the LFR-Generator [17] implemented in NetworKit [19]. These graphs resemble social networks with a community structure.

Artificial. For each artificial graph we picked the number n of vertices uniformly at random between 100 and 1000. The Triangulation+X class contains randomly generated n-vertex triangulations with an additional set of x edges. The number x is picked uniformly at random between 0.1n and 0.15n. The endpoints of the additional edge are picked uniformly at random, as well.

The class 1-Planar consists of graphs that admit drawings where every edge has at most one crossing. We used a geometric and topological procedure to generate these graphs. For the former consider a random point set P of n points. Let \(e_1, \dots e_k\) be a random permutation of all pairs of points in P. Let \(G_0 = (P, \emptyset )\). If the drawing \(G_{i-1} + e_i\) induced by P is simple and 1-planar, we define \(G_i\) to be this graph, otherwise we set \(G_i = G_{i-1}\). We construct the topological 1-Planar graphs based on a random planar triangulation G generated with OGDF [5]. Let v be a random vertex of G and let v, x, u, y be an arbitrary 4-cycle. We add uv to G if \(G+uv\) is 1-planar. The process is repeated x times, for a random number \(x \in [0.3n, 0.4n]\). In contrast to the experimental work on crossing minimization in book embeddings [16], we did not observe that our heuristic performs differently on the topological and geometric 1-Planar graphs. Hence, we merge the two classes into a single class. Thus, in total the 1-Planar graphs contain 200 graphs compared to 100 in the other graph classes.

Crossing angles of the initial drawings.

Full size image

4.2 Initial Drawings

In our evaluation we consider four initial drawings of each benchmark graph; refer to Table 1. A random point set P of size n induces a Random drawing of an n-vertex graph. The Fr+Cos drawings are generated by applying our implementation of the force-directed method of Fruchtermann and Reingold [11] to the Random drawings with the additional \(F_\mathrm {cos}\) force (Sect. 2.1). We applied the stress majorization [5, 12] implementation of the Open Graph Drawing Framework (OGDF) to Random in order to obtain the Stress drawings. The Cr-small drawings are computed with the heuristic introduced by Radermacher et al. [18] in order to decrease the number of crossings in straight-line drawings. They showed that the heuristic computes drawings with significantly less crossings than drawings computed by stress majorization. Unfortunately, within a feasible amount of time we were not able to compute Cr-small drawing for the classes 1-Planar and Triangulation+X.

A point in Fig. 3 corresponds to the crossing angle of an initial drawing. The plot is categorized by graph class. The Random drawings have the smallest crossing angles. The Stress drawings have a larger crossing angle than Cr-small and overall, Fr+Cos drawings tend to have the largest crossing angle.

We point out that in contrast to the evaluation of Argyriou et al. [2], our implementation of the force-directed method with \(F_{\mathrm {cage}}\) and \(F_{\mathrm {ang}}\) produces drawings with smaller crossing angles than with \(F_\mathrm {cos}\). Thus, we do not consider these drawings in our evaluation.

4.3 Differences Between Paired Drawings

In order to compare the performance of two algorithms on multiple graphs and to investigate by how much one of the algorithms outperforms the other, we employ the following machinery. We denote by \(\varGamma \{G\}\) the set of all drawings of G. Let \(\mathcal {G} = \{G_1, G_2, \dots , G_k\}\) be a family of (non-planar) graphs. We refer to a set \(\varLambda = \{\varGamma _1, \dots , \varGamma _k\}\) as a family of drawings of \(\mathcal G\) where \(\varGamma _i \in \varGamma \{G_{i}\}\) . Let \(\varLambda ^1\) and \(\varLambda ^2\) be two families of drawings of \(\mathcal G\). Let \(\mathcal F\) be a subset of \(\mathcal G\). We say \(\varLambda ^1\) outperforms \(\varLambda ^2\) on \(\mathcal F\) if and only if for all \(G_i \in \mathcal F\) the inequality \({{\mathrm{cr\text {-}\alpha }}}(\varGamma _i^1) > {{\mathrm{cr\text {-}\alpha }}}(\varGamma ^2_i)\) holds. If \(\varLambda ^1\) outperforms \(\varLambda ^2\) on \(\mathcal F\) then \(\varLambda ^1\) has an advantage of \(\varDelta > 0\) on \(\mathcal F\) if for all \(G_i \in \mathcal F\) the inequality \({{\mathrm{cr\text {-}\alpha }}}(\varGamma ^1_i) > {{\mathrm{cr\text {-}\alpha }}}(\varGamma ^2_i) + \varDelta \) holds. For a finite set \(\mathcal G\), we say \(\mathcal F\) has relative size at least \(p\in [0,1]\) if \(|\mathcal F| \ge p \cdot |\mathcal G|\).

In order to compare two families of drawings we plot the advantage as a function of p; refer to Fig. 5. For each value p the plot contains 5 five bars, each corresponding to a graph class. The height of the bars correspond to advantages \(\varDelta \) for a set of relative size p. A caption of a figure in the form of A vs B indicates that if \(\varDelta \) is positive, B has advantage \(\varDelta \) over A. Correspondingly, if \(\varDelta \) is negative, A has an advantage of \(-\varDelta \) over B. Thus, Fig. 5 shows that for \(p=0.1\), for each graph class there is a subset \(\mathcal F\) of relative size 0.1, i.e., \(\mathcal F\) contains at least 10 graphs, such that the set Sloppy has an advantage of \(\varDelta \) over Precise on \(\mathcal F\). In greater detail, Sloppy has an advantage of \(7.9^\circ \) over Precise on the North graphs, \(12.9^\circ \) on the Rome graphs, \(11.5^\circ \) on the Community graphs, \(1.2^\circ \) on the 1-Planar graphs and \(1.2^\circ \) on the Triangulation+X graphs. On the other side, Precise has an advantage of \(12.9^\circ \) over \(\textsc {Sloppy} \) on at least 10 North graphs, \(15.7^\circ \) on the Rome graphs, \(13.8^\circ \) on the Community graphs, \(1.1^\circ \) on the 1-Planar graphs and \(0.4^\circ \) on the Triangulation+X graphs. Note that only for \(p < 0.5\) there can be two disjoint subsets \(\mathcal F_1, \mathcal F_2\) of a graph class of relative size p such that Precise has an advantage over Sloppy on \(\mathcal F_1\) and Sloppy has an advantage over Precise on \(\mathcal F_2\).

4.4 Parametrization of the Random Sampling Approach

The Random Sampling approach introduced in Sect. 3 has four different parameters, the number of levels L, the size of the sample T, the initial side length s and the scaling factor b, that allows for many different configurations. With an increasing number T of samples, we expect to obtain a larger crossing angle in each iteration to the cost of an increasing running time. If we allow each configuration the same running time, it is unclear whether it is beneficial to increase the number of iterations or to increase the number of samples (T) and levels (L) per iteration. This motivates the following question: does the crossing angle of a drawing of an n-vertex graph computed by the random sampling approach within a given time limit \(t_n\) increase with an increasing number of samples and levels? We choose to set the time limit \(t_n\) to n seconds. This allows for at least \(1.6 \cdot n\) iterations on our benchmark instances. Since the parametrization space is infeasibly large, we evaluate three exemplary configurations, Sloppy, Medium and Precise; see Table 2.

Performance of different configurations

Full size image

Comparison of the Sloppy configuration to the Medium and Precise configuration. The colors indicate the graph as indicated by Fig. 2.

Full size image

The plot in Fig. 4 does not indicate that the distributions of the crossing angle differ across different configurations significantly . With the plot in Fig. 5 we can confirm this observation. For each configuration there is only a small subset of each class such that the configuration has an advantage over the other configurations. For example, for the Rome graphs there exist at least 10 graphs such that Sloppy has an advantage of \(10^\circ \) over Precise. On the other hand, there are at least 10 different graphs such Precise has also an advantage of \(10^\circ \) over Sloppy. For \(p\ge 0.5\) no configuration has an advantage over the other, or it negligibly small. Thus, we conclude that given a common time limit, increasing the levels and the sample size does not necessarily increase the crossing angle.

Crossing angles of the initial drawings after optimization with the Random Sampling approach.

Full size image

Initial crossing angle vs the final crossing angle. The plots show the crossing angles of the classes North, Community and 1-Planar.

Full size image

4.5 Improvement of the Crossing Angles

In this section we investigate whether the Random Sampling approach is able to improve the crossing angle of a given drawing within 2n iterations. Given the same number of iterations, it is most-likely that we obtain a larger crossing angle of a drawing if we increase the number of samples. Thus, we use the Precise configuration for the evaluation of the above question. We refer to the drawings after the application of the Random Sampling approach as \(\textsc {Random}^\star \), \(\textsc {Fr+Cos}^\star \), \(\textsc {Stress}^\star \) and \(\textsc {Cr}\text {-}\textsc {small}^\star \), respectively.

The plots in Figs. 3 and 6 indicate that the Random Sampling approach indeed improves the crossing angle of the initial drawings. Figure 7 shows the relationship between the crossing angle of the initial drawing and the final drawing. For the purpose of clarity, the plot only shows drawings of the classes North, Community and 1-Planar. The plots shows that the Random Sampling approach considerably improves the crossing angle of the initial drawing. In case of the North graphs there are a few graphs that have an improvement of at least \(70^\circ \). There are at least 10 drawings in Random whose crossing angle is improved by at least \(75^\circ \) . For all real world graph classes and all initial layouts there are 70 graphs in each class, such that the final drawing has an advantage of over \(25^\circ \).

For Triangulation+X, \(\textsc {Fr+Cos}^\star \) has an advantage of at least \(11^\circ \) over Fr+Cos on at least 90 Triangulation+X. For the remaining initial layouts the corresponding advantage is at most \(7.6^\circ \). Considering the 1-Planar graphs the corresponding advantages are \(14^\circ \) and \(9.7^\circ \). This indicates that within 2n iterations a large initial crossing angle helps to further improve the crossing angle of 1-Planar and Triangulation+X graphs. Overall we observe that the 1-Planar and Triangulation+X classes are rather difficult to optimize. This can either be a limitation of our heuristic or the crossing angle of these graphs are indeed small. Unfortunately, we are not aware of meaningful upper and lower bounds on the crossing angle of straight-line drawing of these graphs. Nevertheless, we can conclude that our heuristic indeed improves the initial crossing angle. To which extend our heuristic is able to increase crossing angle of a drawing depends on the graph class and on the initial drawing itself.

4.6 Effect of the Initial Drawing

The Random Sampling approach iteratively improves the crossing angle of a given drawing. Given a different drawing of the same graph the heuristic might be able to compute a drawing with a larger crossing angle. Hence, we investigate whether the choice of the initial drawing influences the crossing angle of a drawing obtained by the Random Sampling approach with 2n iterations.

For all graph classes, except from North, it is apparent from Fig. 6 that the drawings in the set \(\textsc {Random}^\star \) have noticeably smaller crossing angles compared to the remaining drawings. This meets our expectations, since the initial Random drawings presumably has many crossings [15] and thus is likely to have many small crossing angles; compare the initial crossing angles plotted in Fig. 3.

Comparison of the initial layout.

Full size image

The plot in Fig. 6 suggests that the set \(\textsc {Fr+Cos}^\star \) contains drawings with the largest crossing angles. In order to corroborate this claim, Fig. 8 shows crossing angles obtained by different algorithms. It shows that except for one graph, each drawing in \(\textsc {Fr+Cos}^\star \) has a larger crossing angle than the corresponding drawing in \(\textsc {Random}^\star \). Figure 8b and c suggest that \(\textsc {Fr+Cos}^\star \) overall contains more drawings with a larger crossing angle compared to \(\textsc {Stress}^\star \) and \(\textsc {Cr}\text {-}\textsc {small}^\star \). With the help of Fig. 9 we are able to quantify the number of graphs above the diagonal and the difference of the crossing angles. Figure 9a shows that for the graph classes 1-Planar and Triangulation+X, there are each at least 90 of 100 graphs whose drawings in \(\textsc {Fr+Cos}^\star \) have a crossing angle larger then the corresponding drawing in \(\textsc {Stress}^\star \), i.e., \(\textsc {Fr+Cos}^\star \) has an advantage of \(4.5^\circ \) degrees over \(\textsc {Stress}^\star \).

Comparison of the crossing angle of the final drawings.

Full size image

There are at least 50 1-Planar graphs such that the \(\textsc {Fr+Cos}^\star \) has an advantage of \(10^\circ \) over \(\textsc {Stress}^\star \). At least 50 Community graphs have drawings in \(\textsc {Fr+Cos}^\star \) with an advantage of \(5^\circ \) over the corresponding drawings in \(\textsc {Stress}^\star \). There are 10 North graphs such that \(\textsc {Fr+Cos}^\star \) has an advantage of at least \(5^\circ \) over \(\textsc {Stress}^\star \). Vice versa there are 10 different North graph such that \(\textsc {Stress}^\star \) has an advantage of at least \(5^\circ \) over \(\textsc {Fr+Cos}^\star \). Considering subsets of size 10, \(\textsc {Fr+Cos}^\star \) has an advantage of \(20^\circ \) over \(\textsc {Stress}^\star \).

Recall that \(\textsc {Cr}\text {-}\textsc {small}^\star \) does neither contain drawings of the class 1-Planar nor of the class Triangulation+X. The drawings of \(\textsc {Fr+Cos}^\star \) has an advantage of over \(7^\circ \) over \(\textsc {Cr}\text {-}\textsc {small}^\star \) on over 70 Community graphs. For a subset with at least 10 Community graphs, the advantage rises to almost \(25^\circ \). The comparison on \(\textsc {Stress}^\star \) and \(\textsc {Cr}\text {-}\textsc {small}^\star \) shows that drawings with a few crossings do not necessarily yield larger crossing angles. Overall, we conclude that the Random Sampling approach computes the largest crossing angle when applied to the Fr+Cos drawings. This is plausible, since the crossing angles of the initial crossing angles are already good. As shown in the previous section, depending on the graph class, there is a large improvement in the crossing angle, if we start with such an initial drawing. In further investigations we were able to show that the advantages of \(\textsc {Fr+Cos}^\star \) decreases comparably to \(\textsc {Stress}^\star \) with 4n iterations. However, doubling the iterations does not entirely cover the gap between the crossing angles of the initial drawings.

4.7 Note on the Running Time

In this section we shortly evaluate the running time of our algorithm on all our graphs. For this purpose, we applied two implementations of the Random Sampling heuristic to the Random drawings. The Sweep implementation uses a sweep-line algorithm to compute the pair of crossing edges that create the smallest crossing. Bucket uses the algorithm described in Sect. 3.1. We employ the speed-up technique only for graphs with at least 1000 edges, we refer to these graphs as large. Figure 10 plots the running time per iteration for n-vertex graphs. The median and the second 3-quantile of the running time on the large graphs are highlighted. Bucket has an average running time of 391 ms per iteration on the large graphs and Sweep has an average running time of 500 ms. On all graph Bucket requires on average 328 ms per iteration.

Average Running time per iteration vs the number of vertices.

Full size image

(a) Stress drawing of a Rome graph. (b) Drawing after optimizing the crossing angle. The ratio between the longest and shortest edges is large.

Full size image

We designed and evaluated a simple heuristic to increase the crossing angle in a straight-line drawing of a graph. On real world networks our heuristic is able to compute larger crossing angles than on artificial networks. This can either be a limitation of our heuristic or the crossing angle of our artificial graph classes are small. We are not aware of lower and upper bounds of the crossing angle of these graphs. Thus, investigating such bounds of the 1-Planar and Triangulation+X graphs is an interesting theoretical question.

Figure 11 shows that our heuristic does not necessarily compute readable drawings. Nevertheless, parts of the Random Sampling heuristic are easily exchangeable. For example, the objective function can be replaced by a linear combination of number of crossing and the crossing angle. Thus, future work can be concerned with adapting the Random Sampling approach with the aim to compute readable drawings.