Now that we have at least one planarity testing algorithm in our tool belt, we can look at our task, visualizing graphs nicely on screen, with more confidence. Some of the planarity testing algorithms also output a planar embedding, and that gives us a good starting point.
And yet, we have a long way to go.
Let’s start with two considerations:
- Is reducing the number of crossing edges the only criterion we should follow?
- We know not all graphs are planar . . . should we just give up on non-planar graphs?
Let’s focus on the first question. What do you think? Take a minute to imagine what other characteristics make a good visualization and, vice versa, what could go wrong with this.
Then take a look at figure 15.11 to corroborate your thoughts.
Looking at it, we can see that there are at least three different aspects that contribute to the poor look and comprehensibility of the visualization:
- The most evident effect is that it’s impossible to read any text. This is because elements are unnecessarily far from each other, and we need to zoom out to see the whole chart.
- Some edges are all twisted and windy, making it harder to follow them.
- Compared to figure 15.1, the relative position of the elements fails to suggest the direction of flow. Adjacent nodes are far from each other, with nodes modeling other unrelated steps in between.
OK, this is what’s wrong with the chart in figure 15.11. Can we transform these considerations into requirements to have a better visualization? Let’s try this:
- Adjacent vertices (aka vertices connected by an edge) must be placed as close as possible in the plane. Of course, we need some sort of a compromise because we don’t want vertices to get too close (otherwise they would overlap with each other or hide the edge between them), and also if a vertex v is adjacent to many others, we can’t afford too many of these vertices to cluster around v.
- Draw edges in the simplest possible way: either segments or arcs of ellipses should work.
- Reduce the number of edges crossing. Aim for no intersections if a graph is planar or as few as possible for non-planar ones.
In the next chapters, we will see how these requirements can be translated into mathematical expressions to model a cost function that can reflect how good a graph is.
We’ll use the rest of this chapter to talk in more depth about the third point.
As we have seen, there are graphs for which it’s not possible to find an embedding without any edge crossing.
For non-planar graphs G, however, we can define a value, called a crossing number, that is the smallest possible number of edge crossings of all the possible embeddings of G to R2.
Planar graphs, obviously, have a crossing number equal to 0; both non-planar graphs we saw earlier in the chapter, K5 and K33, have a crossing number equal to 1.
1. Finding the crossing number
Kuratowski’s theorem tells us the necessary and sufficient condition for a graph to be planar, but it doesn’t help much with computing the minimum crossing number of non-planar graphs. The problem of finding the crossing number for a non-planar graph has been investigated far less than planarity testing/embedding. While there are several efficient algorithms that provide planar embeddings for planar graphs, to date there isn’t an efficient algorithm that can find the minimum crossing number for generic graphs.
As a matter of fact, it has been proven that determining the crossing number of a generic graphs is an NP-complete problem.
There are, however, notable exceptions[1] if we narrow the field; for example, it has been recently proven that there is a simple algorithm to check if a non-planar graph has crossing number 1.
Assuming that g is a non-planar graph (and hence it has at least 5 vertices, as a consequence of Kuratowski’s theorem), for each pair of non-adjacent edges a→b, c→d, we remove both edges, and add a new vertex v, and 4 new edges a→v, v→b, c→v, v→d.
If the new graph obtained is planar, then the crossing number of the original graph is exactly 1.
Some of the most interesting results in this area focus on complete and complete bipartite graphs. Guy’s and Zarankiewicz’ conjectures postulate a formula for the crossing number of these graphs, but they haven’t been proven so far.
Guy’s conjecture hypothesizes that the minimum crossing number of the generic complete graph with n vertices is given by
Zarankiewicz’ conjecture, however, provides an estimate for complete bipartite graphs with two partitions having n and m vertices, respectively:
As of today, both formulas have been proven to hold as upper bounds, meaning that the crossing number for these graphs is not larger than the value computed using the formulas, and they have not yet been disproved as lower bounds.
If we try to apply these results to the two graphs we have already introduced, we get
So, for K5 and K3,3 the expectation is consistent with what we have mentioned and with our experience. As a matter of fact, Guy’s conjecture has been proven to hold true as an exact value for n ≤ 12, while Zarankiewicz’ for n,m ≤ 7.
If we consider, for instance, graph K6, shown in figure 15.12, the expected (and proven) crossing number is 3.
And yet, it’s significantly harder to obtain an embedding with minimal crossings between edges. An example embedding is shown in figure 15.13
2. Rectilinear crossing number
Have you noticed that so far, we’ve only drawn graphs using segments? While this has served our purpose well, and we’ve always been able to draw graphs with the minimum number of intersections, this is not always true.
In fact, we need to introduce a new definition: the rectilinear crossing number of a graph g is the minimum number of edges crossing in a straight-line drawing of G; that is, an embedding on the plane for G where edges are drawn as straight-line segments.
When we restrict to straight-line segments for the edges, we are using a fraction of the possible embeddings. It shouldn’t be surprising, therefore, that the rectilinear crossing number of a graph is never smaller than its crossing number.
Now, can it be larger? It has been proven that for any graph g with a crossing number smaller than or equal to 3, it’s possible to come up with a straight-line drawing with minimal crossings: in other words, whenever the crossing number cr (G) is 3 or less, it matches the rectilinear crossing number, rcr (G).
Although this is great, because it means that planar graphs can indifferently be drawn as straight-line or curve-line drawings, the result can’t be generalized. There exist, in fact, graphs for which cr(G) = 4 < rcr(G). Figure 15.14 shows the original example used for the proof in a paper from 1993. In the left half of the figure, you can see a straight-line drawing of the graph, with 12 edge intersections. This is also the rectilinear crossing number of the graphs, and no matter how much you move vertices around, you can’t get fewer intersections, as long as you only draw edges with straight line segments.
On the other hand, the right half of figure 15.14 shows that by using cubic Bezier curves and moving a few edges to the external face of the first embedding, we can reduce the number of intersections to just 4; this is also the crossing number for this graph.
The interesting part is that by using this graph as a starting point, it is possible to construct graphs with a crossing number equal to 4, but with a rectilinear crossing number arbitrarily large (potentially up to infinity). For the proof and the construction rules, please refer to the original article.
For complete graphs, it’s known that for n>10, rcr (Kn)>cr(Kn); unfortunately, we can’t do any better for our examples for K5 and K6: even using generic Jordan curves, the best embedding we can get for K6 is the one shown in figure 15.15, which still has three intersections.
Nevertheless, using arcs allows us to choose a simpler and more regular layout for the vertices.
So, long story short, if we draw large graphs using only straight-line segments, chances are that we have to accept a larger number of edge intersections than is actually possible, because the rectilinear crossing number is larger than the crossing number for many graphs. Does that mean we have to dismiss this way of drawing graphs? Not at all!
First, as we have seen, for all planar graphs and all graphs whose crossing number is smaller than 4, we can use the straight-line drawing without any loss; not all the other graphs with cr(G) ≥ 4, moreover, have a worse rcr(G) than their cr(G).
It turns out that for practical purposes, we are often more interested in drawing planar or almost-planar graphs, because flow-charts, PERT diagrams, workflows, and so on are usually fairly sparse graphs, which in turn are less likely to have a high crossing number. After all, from Euler’s invariants we know that planar graphs must be sparse (because the number of edges is linear in the number of vertices).
Second, even if curve-line embeddings can lead to fewer crossing points, it doesn’t mean that it’s easy to find one. As a matter of fact, these drawings are much harder to find with an algorithm because we have to optimize many more parameters. Besides the position of the vertices, we also have to find the ideal curves that reduce the number of intersections. This will add at least one or two parameters per edge, if Bezier’s quadratic or cubic curves are used, making the search space much larger and harder to search. The number of parameters, in fact, goes from O(V) to O(V+E), which in turn is O(V2) in the worst case.
Third, using curves requires a larger computational power. The algorithm to check if two segments intersect is significantly easier than checking if two curves do (and it can be made even easier with some restrictions on the position of the vertices). This means that even computing the number of intersections in a candidate solution is more expensive with curve-line drawings.
In the next chapters, we will focus on straight-line drawings, but we’ll also show how to extend them to curve-line graphs.
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)