A planar orthogonal graph drawing is a drawing that can be embedded in a plane without crossings, whose vertices have a degree of no more than 4, and whose edge's connectivity always make angles of 90, 180, or 270 degrees. These graphs have many uses like drawing schematics for circuit layout problems. An important issue in making these drawings is to keep them as simple as possible while still keeping the desired connectivity. Simplicity, in this case, is a drawing with a minimum number of bends.
The strategy for bend minimization in planar orthogonal drawings can be best understood with a complete walk through of the procedure. This procedure involves two steps. The first step requires a curve C to be placed onto a given planar orthogonal drawing D. This curve C is placed such that it intersects vertices and edges based on given constraints which enable the consistency of the drawing to be preserved. The next step is to add and remove bends based on C so as to reduce the number of bends and simplify the drawing. Let's say we have the following drawing:
Since the drawing is orthogonal, there are 3 types of angles that are represented. Inflex angles are angles that are 90 degrees, flat angles are angles that are180 degrees, and reflex angles are angles that are 270 degrees[3]. These angles are named when the given curve C enters the drawing by crossing edges or intersecting vertices. As we go through the bend minimization process, there are some rules that must be followed. First, a curve can only intersect a vertex by entering from a flat or reflex edge. The following equation tells us if a given curve can minimize bends in a drawing[3].
If the delta C is negative then we can minimize the bends along the curve C. If delta C = 0 then the curve C is trivial and there will be no change to the drawing. Finally,if delta C is positive then the bends under that curve are already minimized. If the drawing can be minimized then there are three simple rules to follow in reconstructing the drawing. First, if the curve crosses an edge by entering a 270 degree angle, then remove the bend. Second, if the curve crosses an edge by entering a 90 or 180 degree angle, then add a bend. Third, if the curve intersects a vertex and the intersection angle is greater than 180 degrees[2], then rotate the edges on one side to reduce the angle from which the curve entered and increase the angle that the curve exited[1]. The next series of figures demonstrates the bend minimization process.
The curve enters the drawing at position one which is a 270 degree angle. So reflex(C) is set to 1. At position 2, C also enters the edge at a 270 degree angle resulting in reflex(C) being set to 2. At position 3, C leaves the graph at an angle of 180 degrees, so flat(C) is set to 1. As a result,
This delta C states that C gives us one less bend. So, let's reconstruct the drawing based on the three rules given previously. Note that in the following figures, dotted lines represent edges that were in the original drawing but now have been placed elsewhere due to minimization.
At position 1, the bend is removed.
At position 2, the bend is also removed.
At position 3, we add a bend. Notice that we keep the connectivity between vertex H and vertex G by moving G along with the bent edge. We call this translated vertex G'. Also note that G could have been translated to G' during bend removal at position 1 or position 2. As long as the correct connectivity is maintained during stretching, it makes no difference.
At this point, we remove the dotted lines and shorten and stretch the newly drawn lines while maintaining the connectivity of the original graph to complete the drawing.
This new drawing has 5 bends where the original drawing had 6. We can perform one more bend minimization on the drawing.
We enter the drawing with curve C at position 1 at an angle of 270 degrees. So we set reflex(C) equal to 1. At position 2 we also enter the edge at an angle of 270 degrees. This sets relfex(C) equal to 2. At position 3 we enter vertex F. This entrance is a legal move since we are not entering an angle of 90 degrees and does not contribute to the delta C. Finally at position 4, we enter a flat edge at an angle of 180 degrees so we set flat(C) equal to 1. After position 4, the curve exits the drawing. Using the delta C equation, we get
We can have one fewer bend due to the curve. At position 1, we remove the bend.
At position 2, we also remove the bend.
At position 3, the curve intersects a vertex. This is a legal intersection since the intersection angle is 270 degrees. We must rotate the edges on one side of the curve by 90 degrees to reduce the angle from which the curve entered the vertex , and increase the angle through which the curve exited[1]. In this case, we rotate edge FH 90 degrees to the right.
At position 4, we add a bend.
At this point, we remove the dotted lines and shorten and stretch the newly drawn lines while maintaining the connectivity of the original graph to complete the drawing.
This drawing has the minimum number of bends based on Theorem 8.6[3]. The original drawing started with 6 bends. The final drawing has only 4 bends.
When testing whether a given curve can minimize bends in a planar orthogonal graph drawing, it is difficult to draw numerous curves using pencil and paper because once a curve is drawn it has to either be erased or a identical drawing must be created in order to draw another curve. This is especially tedious when dealing with very complex drawings. I have created an applet that allows users to create planar orthogonal graph drawings and then explore bend reduction possiblities easily by allowing for the drawing of as many curves as needed without the need for redrawing the graph. The applet, using the rules involved with bend minimization, determines whether the given curve can reduce the number of bends in the drawing and shows the user where bends should be added or removed based on a set of color coded annotations. The applet is useful for those users who quickly want to draw a graph and see if they can minimize it, and it is also useful on an educational basis for those who want to understand the concepts behind bend stretching and minimization of planar orthogonal drawings.
Go to The Planar Orthogonal Graph Drawing and Bend Reduction Tester
[1] Tamassia, Roberto "Minimizing the Number of Bends in Orthogonal Draw ings", Computational Geometry, Lecture 19, April 19, 1993.
[2] Tamassia, Roberto "Constraints in Graph Drawing", Lecture Slides, Spring 1997.
[3] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis, Graph Drawing, Chapter 8, Prentice-Hall, to appear.