Graphs are an amazing data structure. In chapter 14 we just scratched the surface, talking about Dijkstra’s and A*, and there are many other cool applications for graphs. You must have heard of knowledge graphs,[1] or graph databases such as Neo4J, just to name a few that are hyped these days.
But graphs are also used to model more tangible applications; for example, a printed circuit board can be represented as a graph, where electronic components are the vertices, and conductive tracks on the board (usually made out of copper) are the edges. Besides that, we as humans often need to visualize a graph for better comprehension. Consider, for instance, a flow chart (which, not surprisingly, is a graph), like the one shown in figure 15.2.
When we can visualize it, it’s easy both to follow the flow and to get a high-level idea of its overall structure. Check out its formal definition, in terms of graph’s vertices and edges:
G = (
V = [Start, A, B, A==B, A<B, swap(A,B), A=A-B, Output: B, End],
E = [Start -> A, A -> B, A==B -[Yes]-> Output: B, A==B -[No]-> Output: B,
➥ A<B -[Yes]-> swap(A,B), A<B -[No]-> A=A-B, swap(A,B) -> A=A-B, A=A-B ->
➥ A==B, Output: B -> End]
)
Was it as easy to understand as looking at its drawing?
- think that we can agree there is fundamental value in drawing graphs, at least when we are supposed to understand and manually process them. Although this is not always the case,[4] there are many examples where we do want to visualize graphs, for instance in flow charts, UML diagrams, PERT charts, and so on.
The next thing we need to agree (or not) upon is that not all visualizations are equally useful. Look at figure 15.3 and compare it to figure 15.2. I don’t know about you, but rather than using the diagram in figure 15.3, I might as well look at the definition of the graph: that’s how confusing it feels.
Figure 15.3 The same flow chart as in figure 15.2, but with a different layout. Can you still make sense of it?
The key difference between the two layouts is that in figure 15.3, edges cross each other multiple times, making it difficult to follow them. In figure 15.2, no edges were crossing—this is a planar embedding for a planar graph! Don’t worry, we’ll define those in a minute. Before that, there is one further consideration: the drawing could get even worse, if you think about it—at least in figure 15.3, edges don’t overlap with vertices.
1. Some basic definitions
In the previous section, we saw how drawing a graph without intersections between its edges makes the visualization a lot clearer. But is it always possible to do so to avoid these intersections?
Hold on to this question; we’ll come back to it. Meanwhile, we can look at a couple of definitions that we’ll use during this and later chapters.
Drawing a graph on a plane can be thought of as placing vertices on a 2-D Euclidean space. Informally, we can imagine each vertex as a point in R2 (the set of all pairs of real numbers), and each edge as an arc (or a polyline) between two vertices.
More formally, we can define a planar embedding as an isomorphism (a 1:1 mapping) between an abstract graph g and a plane graph G’.
A plane graph, in turn, is defined as a pair of finite sets (V, E), denoted as vertices and edges respectively, such that
- V is a subset of R2.
- Every edge e e E is a section of a Jordan curve passing through two vertices.
- No two edges have the same pair of endpoints.
- No edge intersects a vertex (other than its endpoints) or any other edge.
We still owe you a definition: a Jordan curve is a planar, simple and closed curve, a non-self-intersecting continuous loop in the plane. See figure 15.4 for a few examples.
A planar graph is thus defined as an abstract graph G for which there exists a planar embedding.
Now back to our question, which we can reformulate using our definitions: Are all graphs planar?
The answer is, unfortunately, no, not all graphs are planar. The first algorithm to check whether a graph is planar was given by the Polish mathematician Kazimierz Kura- towski; his theorem characterizes planarity in terms of forbidden graphs. It states, in fact, that for a graph to be planar, it can’t contain two specific non-planar graphs as its subgraphs.
These two graphs are the simplest non-planar graphs: the complete graph k5 and the complete bipartite graph K33; Kuratowski’s theorem states that “a graph is planar if and only if it doesn’t contain as a subgraph neither K5 nor K3, 3, nor any subdivision of those two graphs.”
This was an amazing result, but to appreciate it better, we should first consider a few more definitions.
2. Complete and bipartite graphs
A complete ggraph is a graph where each vertex is connected by an edge to each other vertex in the graph. In these graphs, the number of edges is maximal for simple graphs, being quadratic with respect to the number of vertices: |E| = O(|V|2).
Notice, however, that a complete graph doesn’t contain loops; therefore, the exact number of edges of a complete graph with n vertices is n * (n-1) / 2, where |V| == n.
Complete graphs are denoted with the letter K, from Kuratowski’s initials, and a subscript that indicates the number of vertices in the graph; therefore, K5 (figure 15.5) denotes the complete graph with 5 vertices, and in general, Kn is the complete graph with n vertices.
A bipartite graph is a connected graph where vertices can be partitioned into two groups, let’s call them A and B, such that vertices in group a are only connected to vertices in group B (in other words, each vertex in group A can’t have any edge to another vertex within group A, and likewise for group B).
A complete bipartite graph just has all the possible edges between the two groups of vertices—again, loops are not allowed.
Kn,m is the generic complete bipartite graph with two partitions of n and m vertices each, and K3,3 (figure 15.6) is the complete bipartite graph with two partitions having 3 vertices each.
A complete bipartite graph whose partitions have size n and m has exactly n * m edges.
The generic embedding (not necessarily planar) is defined similarly to what we did in the previous section; it’s an isomorphism r between a graph G and a subset G’ = (V,E) of R2, such that:
- V is a subset of R:
- Every edge e e E is a section of a Jordan curve between two vertices.
- No two edges have the same pair of endpoints.
- No edge intersects a vertex (other than its endpoints).
Basically, with respect to the definition of a plane graph and planar embedding given in section 15.1.1, we only waive the requirement that no edges can ever cross.
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)