Orthogonal Drawing Models

Introduction to Orthogonal Drawing Models

What is an orthogonal graph drawing? Most people have a good understanding about what “orthogonal” means. At a first glance, this seems to be an easy question to answer: an orthogonal drawing is a drawing where all edges consist of horizontal and vertical line segments.

Here is an example orthogonal graph drawing showing a model-based engineering diagram of a vehicle wheel assembly.

An orthogonal drawing of a vehicle wheel assembly.

This article discusses use cases that benefit from orthogonal drawings, and delves into various methods developed for creating orthogonal drawings along with the advantages and limitations of each method.

Use Cases of Orthogonal Drawings

Let’s take a look at a few examples where orthogonal graph drawings are used to visualize complex relationships.

Entity Frameworks

Visual Studio and similar development environments use Entity Frameworks to illustrate the architecture of a software program. Here is an example:

An example of Entity Frameworks showing the structure of a software program.

Systems Engineering

Systems Modeling Language (SysML) is a widely used standard when it comes to visualizing the engineering design of complex systems. Here an example of a Block Definition Diagram:

A SysML Block Definition Diagram showing an engineering system.

Project Management

Dependencies between tasks are a key concept in project management. Many standards have been developed to help project managers understand these dependencies. One of the most used are PERT diagrams. Here is an example:

An example of a PERT diagram used in project management.

Techniques for Orthogonal Graph Drawings

Let’s use the K5 (complete graph with 5 nodes) as an example to draw it as an orthogonal drawing. Here is a non-orthogonal drawing of the K5. How can we draw this graph orthogonally? The following sections explore this question using various techniques.

A non-orthogonal drawing of the K5 showing sloped edges.

The Unlimited Growth Model

A first answer to our question could be the “unlimited growth model”.

Definition of the Unlimited Growth Model

In this model, every node is stretched to a size that allows to draw all edges as straight lines. Edges are rendered on a grid, and node centers are positioned on grid points, too. But nodes can have any size. A node can cover many grid points.

Here is a possible result of the K5 example:

The K5 model converted to an orthogonal graph using the Unlimited Growth Model.

Advantages and Limitations of the Unlimited Growth Model

You might consider this method as cheating. But if orthogonality of the edges is the only condition of an orthogonal drawing, then the above is an orthogonal drawing. Each edge is either a simple horizontal line or a simple vertical line. Typically, these drawings look very clear and clean. But increasing the node sizes by that much can be very undesirable, for example when we want to see the node as an image.

The Degree-4 Model

You may prefer nodes to be small, such as a point or a small square. With this additional rule, here is a possible orthogonal drawing of the K5:

An orthogonal drawing of K5 with fixed node size.

Let’s call this the degree-4 model; we will see soon why I chose this name.

Definition of the Degree-4 Model

Similar to the Unlimited Growth Model, in this model, nodes are positioned on grid points and edges run along grid lines. Each node is a square if the same size. Only one edge can attach at each node’s side. And all edges consist of horizontal and vertical segments.

Advantages and Limitations of the Degree-4 Model

Does this model have any disadvantages? For sure. One problem is that by forcing the edges attaching to the same node to use different node sides (it is not allowed that two edges attach at the left side of the same node), we force the drawing to have many bend points.

Using the example above, we have 12 bend points. Bend points often make it difficult to understand the drawing. It is an important optimization criterion for orthogonal drawings to keep the number of bends small. And, more importantly, in the degree-4 model we cannot draw a graph that has nodes with a degree of more than 4 (thus the name of the model) because each node only has four sides available where edges can attach.

The GIOTTO Model

In the GIOTTO Model we allow nodes with a high degree to grow.

Definition of the GIOTTO Model

One idea to extend the degree-4 model to graphs with larger degree is the following technique: when we have a node with large degree, we replace the node with a set of nodes so that each of the new nodes has a degree of four or less:

In this example, we replaced the large degree node in the left drawing with multiple small degree nodes.

Now we can use the degree-4 model and render the red nodes as one large node. We call this model the GIOTTO model, which is the name chosen by the inventor of the algorithm.

Advantages and Limitations of the GIOTTO Model

Did we now find the perfect model? Hardly. One disadvantage of the GIOTTO model is that it does not limit the size of the big nodes. Let’s make an example. This is the graph, not yet in an orthogonal model yet:

A non-orthogonal graph with a variety of nodes.

Node v has a degree of five, so we replace it with four smaller nodes:

Node v is replaced with four smaller nodes.

Now we apply the degree-4 model and get this:

We have converted the graph to an orthogonal layout using the degree-4 model.

When we replace the red nodes with one large node, we can optimize that node’s height, but the width cannot be reduced:

We have replaced the four nodes with the original node, which is very wide.

Even though v only has a relatively small degree of five, the node’s width can grow without limit, depending on the structure of the graph.

The Kandinsky Model

This brings us to the Kandinsky model, again named by the inventor who also happens to be the author of this article.

Definition of the Kandinsky Model

In the Kandinsky model of orthogonal drawings we allow nodes to grow, but only as much as necessary to allow the edges to attach. More precisely, we use two grids: a node grid where the nodes are positioned, and an edge grid where the edges are routed. The edge grid is finer grained than the node grid.

An example graph using the Kandinsky model, showing a node grid and an edge grid.

In the Kandinsky model all nodes are squares of the same size, and that size is determined by the largest number of edges attaching to any node at the same node side.

Advantages and Limitations of the Kandinsky Model

Unlike in the GIOTTO model it is not possible that nodes grow larger due to the structure of the graph.

Here is an example for how the K6 could look like in the Kandinsky model:

The K6 in the Kandinsky model, showing the fine grained edge grid.

If you compare this to the degree-4 model (which would not even be able to handle the K6) you see that nodes can have several edges attached to the same node side. This leads to a lot less bends; in this example there are even no edges with more than one bend. However, since all nodes have the same size, we can see low-degree nodes that are much larger than they have to be, wasting space.

Flexible Node Size and Slope-end Edges

All models discussed so far had one thing in common: the algorithm determines the size of the nodes. But in many applications the node size is an input constraint that has to be maintained. So how could a model look that allows node sizes to be different, but not be changeable by the algorithm? There is one immediate problem that needs to be addressed: if a node has a small size, but a large number of edges attached to it, then what? These edges would be very close together, maybe even overlapping. It would be hard for a user to distinguish them. How can we get out of this?

The answer is: slope end routing. What? Didn’t we say in the very beginning of this article that in an orthogonal drawing we require all edges to consist of horizontal and vertical segments? Yes, true, but to solve hard problems we need to make concessions.

Defining how to allow slopes in certain crowded areas is a complex topic by itself. The main idea is to first allow the algorithm to grow nodes, leading to a true orthogonal drawing; and then shrink the enlarged nodes back to their original size, introducing slope segments. I will show four different results for the same graph, the “Maltese cross”.

Short slopes

In this model we only allow nodes to grow as much as absolutely necessary for their degree. This leads to slopes in a very close neighborhood of high-degree nodes. As a result we get more bend points, but the slopes are as short as possible.

A short slopes model of the Maltese cross, showing more bend points.

Limited slopes

In this model, we allow nodes to grow a little larger than they absolutely must. But we limit node growth for all nodes to be no larger than the necessary size for the largest node. This is the Kandinsky model. Slopes are allowed to be a little longer than absolutely necessary, for low-degree nodes; but they are still confined to be in a close neighborhood of the node. This model leads to less bend points than the “short slopes” model.

The limited slopes model, which allows nodes to grow a little larger but has fewer bend points.

Controlled slopes

In this model we allow nodes to grow larger, defined by the structure of the graph rather than a node’s degree. This is the GIOTTO model. It leads to longer slope segments, but keeps the number of bend points smaller.

The controlled slopes model, which has fewer bend points but longer slope segments.

Any slopes

In this model we allow slopes of any length. The only limitation is that slopes are only allowed for nodes with a degree of more than four, and each slope segment is connected to one such node. The results are fewer bend points (in the example of the Maltese cross we do not need any bend at all), but the resemblance to an orthogonal drawing in the classical sense can get lost.

The any slopes model has few bend points but lacks resemblance to an orthogonal drawing.

Benefits of Orthogonal Drawings

We talked a lot about orthogonal drawings. Why would we prefer these over non-orthogonal drawings? One reason is empiric: as a human observer we can often understand the structure of a graph much better when the edges are drawn orthogonally. It increases the clarity and cleanness of the drawing. Structural details such as symmetries can be recognized much more easily.

But there are also very objective reasons why an orthogonal drawing is preferred or even necessary. For example, if the graph describes the design of a VLSI structure (a computer chip), then the technology dictates that all connections run horizontal or vertical. Another example is optical data transfer where light is transmitted through glass cables, and these have to follow an orthogonal path due to technological necessity or at least long-year convention.

But orthogonal drawings also have an additional advantage: they provide simple metrics that tell us which drawings are better or worse than others. Some of these metrics are:

• The number of edge crossings
• The number of edge bends
• The total length of all edges
• The length of the longest edge
• The total area of the drawing (more precisely: the total area of the smallest rectangle circumscribing the drawing)

The existence of these metrics helps us develop algorithms that optimize a drawing to these criteria, and also easily decide which of several valid drawings is the best.

Conclusion

What do we do at Tom Sawyer Software? A bit of everything. We are always looking for the best solution for any practical use case. Here is an example showing the network of actors having played in “Matrix” movies. It shows nodes of different sizes and a slope model.

A Tom Sawyer Software orthogonal graph drawing showing actors from the Matrix movies.

Are you still reading? Congratulations! You experienced a typical day of working at Tom Sawyer Software. This is our daily bread. We are constantly researching the best ideas for producing readable graph drawings, making it easy for analysts to understand the information that is hidden in a graph.

Frequently Asked Questions

Other Drawing Models

Question: What other drawing model styles exist besides Orthogonal?

Answer: Countless other models can be used, among them:

• Hierarchical models where nodes are positioned in layers
• Concentric models where nodes are positioned on concentric circles
• Circular models where nodes are partitioned into groups and each group’s nodes are positioned on a circle
• Force-driven models where nodes push each other away but get drawn together by their connecting edges
• Bundle models where edges sharing one end node are bundled together
• Hyperbolic models where nodes are positioned on the surface of a sphere
• Many more

Algorithmic Performance

Question: What is the computational complexity of algorithms producing “good” Orthogonal layout?

Answer: Most optimization problems about Orthogonal drawings are NP-hard. This means that implementing any algorithm that produces an optimal solution (like minimizing the number of crossings or bend points) has exponential complexity and is not suitable for practical use. Therefore, most algorithms that are used in commercial products are heuristics that try to find “good” results, but will not find “optimal” results.

Constraints

Question: Are the described Orthogonal drawing models sufficient for use in practical applications?

Answer: No, they are not. Typical real-world scenarios where orthogonal drawings are expected have more requirements that have to be fulfilled. Some examples include

• Nodes have different sizes, defined by the application (for example to fit an image or some text inside the node)
• Edges attach to their end nodes at specified node sides (for example when the edge attaches at a physical object such as a port)
• Certain nodes functionally belong together and should be positioned as a group
• Edges are directed and the node positions should reflect a flow (top-to-bottom or left-to-right) defined by the edges
• Nodes have different shapes (not just rectangles), and the edges have to attach at the shape border rather than at the border of the shape’s bounding rectangle

For commercial algorithms to be successful, they must consider requirements like these (and many more), further increasing the complexity of the problem to be solved.

About the Author

Ulrich Foessmeier has played an influential role in the success of Tom Sawyer Software both in recent and past years. He rejoined Tom Sawyer Software in 2017 as the Vice President of Engineering, where he applies his twenty years of experience in the software industry managing large, and complex product development projects and global engineering teams. From 1997–2011 he worked at Tom Sawyer Software in various roles from Orthogonal layout specialist in the Graph Layout group to Vice President of Engineering, and finally to General Manager of the German office. Further contributions within these years included redesigning and modularizing the entire code base, establishing a defect tracking tool, and building new Tom Sawyer Software teams in Europe.