Backstory behind the dive into the rabbit-hole
About a few months ago I was introduced to the problem of drawing “aesthetically-pleasing graphs where edges have 90 degree bends.” I was incredibly frustrated then as I had to deliver a code that will take in an excel file and export a nice looking graph, and the only clue I had was the aforementioned request with no data or examples. I had to start with no training or background in this area. I would try to search for clues and was frequently left with no leads. I would spend nearly a month trying to formulate the problem from scratch, not realizing that the problem was way more complex than I thought. Each educational resource would be built on the foundation of many more papers and texts, and those too would reference yet more ideas and concepts. Not wanting to let those months go to waste, I thought I would start writing on some of these things.
What are Orthogonal Graphs?
An orthogonal drawing of a graph is a graph representation such that its edges are composed of lines parallel to the vertical or horizontal axis, and in each edge (which could be composed of many of such lines) the lines are connected via 90-degree bends.
Below is an example of an orthogonal graph:
Its quite a nice looking graph isn’t it? Its not immediately obvious why the above graph would look good. What would a bad graph look like? Perhaps the lines would cross very often, making it difficult to trace an edge. Or perhaps a bad graph would have nodes and/or edges that are bunched up together, making it hard to distinguish nodes and edges. From these simple observations, we know that aesthethic looking graphs must have the components evenly-laid out, and also have the lines not cross.
If you sat down to try to draw the above graph from scratch using the prior observations, you would soon face a whole slew of conundrums:
- Let’s suppose that you want to place a node on the surface. Which node do you start with? How would you place the nodes such that you can route the edges well?
- If placing the nodes need you to route the edges well, but you can’t route the edges without some nodes on the screen, how can you even go about it?
- Perhaps we can randomly place the nodes on the surface and iteratively re-draw the edges and then adjust the nodes accordingly
- Then moving one node would affect how to draw its edge, which would affect the edges drawn near to those edges, which affect the nodes attached to all these edges, which affects…
You see? The problem is tough to model because every component is dependent on each other. You cannot solve this problem with a local heuristic.
An Other-worldy Solution
Instead of attacking the problem in a naive way like before, Roberto Tamassia, a legend in the world of graph drawing, laid out an approach in 1987 called the Topology-Shape-Metrics approach. The three properties are defined to be:
- Topology: the sequence of edges along the faces of the drawing (faces are formed when a set of edges results in an enclosed region of the graph) that does not change even if we change the shape of edges (aka introduce bends)
- Shape: A shape of the drawing is derived from the topology and the only thing that is allowed to change is the length of each edge
- Metrics: 2 drawings share the same metrics if they are congruent (we can flip, rotate, shift the drawings such that they overlay on top of each other)
At first glance it doesn’t seem clear how these properties can help us. If we look closely, it breaks down the required properties of a graph into incremental properties, each building from the previous property. The topology of a graph, though an abstract concept, tries to find what is similar between 2 drawings of a graph at the most fundamental level. Without considering additional properties, it is easier to find a graph that shares the same foundational topology with the optimal orthogonal drawing rather than immediately jumping to finding the exact metrics of the optimal orthogonal drawing itself (which was what we tried to do from scratch earlier).
How then can we find the topology of a graph? The graph embedding becomes the next most important concept. A graph embedding is defined to be the circular order of adjacent edges around each node of the graph. Because the embedding is deeply tied to the topology, we can try to find the embedding of the graph (aka the order of the graph) in order to find the optimal topology of the graph. By choosing a good embedding, it gives us the direction to draw a good orthogonal graph. But how can we find a good embedding? A 3 step algorithm is used to progressively bring us from the topology to the metrics of a good orthogonal drawing.
- Planarization: the graph is made into a planar graph by introducing a dummy node for each edge crossing. The attempt to planarize a graph gives an embedding that minimizes edge crossings. But any planar embeddings by themselves are insufficient as we can still organize the faces such that the final planar embedding can have maximum-outer face and minimum-depth. This almost gives us the optimal topology of the graph.
- Orthogonalization: attempt bend minimization by re-formulating the problem as a network-flow problem. This gives us only how many bends there are on each edge, but not where to place those bends.
- Compaction: find where to place the bends by minimizing the length of each line in an edge. This is also another network-flow problem. Finally, the dummy nodes are removed.
Though we do not yet have the coordinates needed to draw the orthogonal drawing, we know where each node is supposed to be placed relative to another node (by the circular order), and we know how many bends there are on each edge, and how long each line has to be between a node and a bend (and also between bends). There is now enough information to draw an orthogonal graph drawing.
Notice how the process is still covered with very broad-strokes. We did not go into detail on how planarization, orthogonalization or compaction could be done. Each of these steps require complex algorithms to solve their specific problems. Without setting some hard restrictions, we would be left with solving a few NP-hard problems just to produce a good-looking orthogonal graph! But alas, I have reached the end of this article. Next time, I will show you how we can produce orthogonal graphs with some code!