Interactive Orthogonal Graph Drawing.
AbstractMany applications require human interaction during the design process. The user is given the ability to alter the graph as the design progresses. Interactive Graph Drawing allows the user to dynamically interact with the drawing of a graph. In this paper, we discuss features that are essential for an interactive orthogonal graph drawing system. We also describe some possible interactive drawing scenarios, present results on two of them, and compare their performance.
Introduction
Graphs have been extensively used to represent various important concepts or objects. Examples
include parallel computer architectures, networks, state graphs, entity-relationship
diagrams, subroutine call graphs, automata, data-flow graphs, Petri nets, VLSI circuits,
etc. In all of these cases, we require that the graph be represented (or drawn) in the plane
so that we can understand and study its structure and properties. It is for this reason that,
typically, the drawing of a graph is accompanied by optimizing some cost function such as
area, number of bends, number of edge crossings, uniformity in the placement of vertices,
minimum angle, etc. For a survey of graph drawing algorithms and other related results see
the annotated bibliography of Di Battista, Eades, Tamassia and Tollis [4]. An orthogonal
drawing is a drawing in which vertices are represented by points of integer coordinates and
edges are represented by polygonal chains consisting of horizontal and vertical line segments.
In this paper we focus our attention on interactive orthogonal graph drawing.
In [19] and [21] it is shown that every biconnected planar graph of maximum degree four
can be drawn in the grid with 2n bends. If the graph is not biconnected then the total
number of bends rises to 2:4n + 2. In all cases, no more than four bends per edge are
required. The algorithms of [21] take linear time and produce drawings, such that at most
one edge may have four bends. Kant [9] shows that if the graph is triconnected of maximum
degree four, then it can be drawn on an n \Theta n grid with at most three bends per edge. The
total number of bends is no more than b 3nc + 3. For planar graphs of maximum degree
three it is shown in the same paper that a gridsize of d n
2 e is sufficient and no more
than are required. In this case, no edge bends more than twice. Even and
Granot [6] present an algorithm for obtaining an orthogonal drawing of a 4-planar graph
with at most three bends per edge. If the embedding of a planar graph is fixed, then an
orthogonal drawing with the minimum number of bends can be computed in O(n 2 log n)
time [20]. If the planar embedding is not given, the problem is polynomially solvable for
3-planar graphs [5], and NP-hard for 4-planar graphs [8]. There is a lower bound of 2n
bends for biconnected planar graphs [22].
Upper and lower bounds have been proved in the case when the orthogonal drawing of the
graph is not necessarily planar. Leighton [10] presented an infinite family of planar graphs
which require
area\Omega\Gamma n log n). Independently, Leiserson [11] and Valiant [23] showed that
every planar graph of degree three or four has an orthogonal drawing with area O(n log 2 n).
Valiant [23] showed that the orthogonal drawing of a general (nonplanar) graph of degree
three or four requires area no more than 9n 2 , and described families of graphs that require
presented an algorithm which constructs orthogonal drawings of
graphs with at most two bends per edge. The area required is 2n \Theta 2n. A better algorithm
is presented in [1] and [2], which draws the graph within an n \Theta n grid with no more than
two bends per edge. This algorithm introduces at most 2n bends.
Recently, we presented an algorithm that produces an orthogonal drawing of a graph of
maximum degree four that requires area at most 0:76n 2 [15]. This algorithm introduces at
most while the number of bends that appear on each edge is no more than
two. If the maximum degree is three, then we have another algorithm which produces an
orthogonal drawing that needs area at most 1n 2 and b n
bends [15, 16]. In this drawing,
no more than one bend appears on each edge except for one edge, which may have at most
two bends.
In all of the above, the drawing algorithm is given a graph as an input and it produces
a drawing of this graph. If an insertion (or deletion) is performed on the graph, then we
have a "new" graph. Running the drawing algorithm again will result in a new drawing,
which might be vastly different from the previous one. This is an inefficient use of time and
resources from two points of view: (a) the time to run the algorithm on the new graph,
and (b) the user may have spent a significant amount of time in order to understand and
analyze the previous drawing. We investigate techniques that run efficiently and introduce
minimal changes to the drawing.
The first systematic approach to dynamic graph drawing appeared in [3]. There the target
was to perform queries and updates on an implicit representation of the drawing. The
algorithms presented were for straight line, polyline and visibility representations of trees,
series-parallel graphs, and planar graphs. Most updates of the data structures required
O(log n) time. The algorithms maintained the planarity of the drawing. The insertion of a
single edge however, might cause a planar graph to drastically change embedding, or even
to become non planar.
An incremental approach to orthogonal graph drawing was presented in [13], where the
focus was on routing edges efficiently without disturbing existing nodes or edges. Layout
adjustment methods were proposed in [14] for rearranging a diagram to avoid overlapping
nodes, and for changing the focus of interest of the user in a diagram. The layout adjustment
methods of [14] have the property that they preserve the user's ``mental map'', that is the
way that the user "visualizes" and "understands" the drawing.
In this paper we investigate issues in interactive graph drawing. We introduce four scenaria
for interactive graph drawing, and we analyze two of them. These scenaria are based on
the assumption that the underlying drawing is orthogonal and the maximum degree of any
vertex is four at the end of an update operation.
We show that in one scenario (Relative-Coordinates), the general shape of the current
drawing remains unchanged after an update is performed. The coordinates of some vertices
and bends of the current drawing may shift by a total amount of at most 6 units along the
x and y axes. Linear programming is employed to prove upper bounds on the area and the
number of bends for this scenario. More specifically, an interactive graph drawing system
under the Relative-Coordinates scenario builds a drawing that has no more than
bends when the graph is connected at all times, and no more than 4n(t) bends otherwise.
The area of the drawing is never larger than 2:25n(t) 2 when the graph is connected at all
times, and no larger than 3n(t) 2 otherwise. Note that n(t) is the number of vertices that
have been inserted to an initially empty graph up to time t. No edge has more than 3 bends
at any time during the drawing process. Results regarding the performance of this scenario
when the very first update operation applies to a non-empty graph are also presented.
In another scenario (No-Change), we discuss an interactive graph drawing technique for
building an orthogonal drawing of a graph from scratch, so that any update operation
inserts a new vertex and routes new edges in the drawing without disturbing the current
drawing. Analyzing the performance of the No-Change scenario reveals that the area of the
drawing at any time t is no more than 1:77n(t) 2 when the graph is connected at all times,
and no more than 4n(t) 2 otherwise. Note that n(t) is the total number of vertices at time t.
Apart from the area, this scenario has good behavior in terms of the total number of bends
as well, which are no more than 2:66n(t) when the graph is connected at all times, and
no more than 4n(t) otherwise. At most 3 bends may appear on any edge of the drawing,
any time.
In Section 2 we give an example of some features that an interactive drawing system should
have. In Sections 3 and 4 we analyze two interactive graph drawing scenaria (i.e., Relative-
Coordinates and No-Change), and present our results on their performance. In Section 5
we compare these two scenaria in terms of their performance, and discuss some extensions.
Finally, Section 6 presents conclusions and open problems.
Interactive Scenaria
Software which supports interactive graph drawing features should be able to: (a) create
a drawing of the given graph under some layout standard (e.g., orthogonal, straight line,
etc.), and (b) give the user the ability to interact with the drawing in the following ways:
ffl insert an edge between two specified vertices,
ffl insert a vertex along with its incident edges,
ffl delete edges, vertices or blocks of vertices,
ffl move a vertex around the drawing,
ffl move a block of vertices and edges around the drawing.
The drawing of the graph that we have at hand at some time moment t is called current
drawing, and the graph is called current graph. The drawing resulting after the user request
is satisfied is called new drawing. There are various factors which affect the decisions that
an interactive drawing system takes at each moment a user request is posted and before the
next drawing is displayed. Some of these factors are the following:
ffl The amount of control the user has upon the position of a newly inserted vertex.
ffl The amount of control the user has on how a new edge will be routed in the current
drawing connecting two vertices of the current graph.
ffl How different the new drawing is, when compared with the current drawing.
Keeping these factors in mind, we propose four different scenaria for interactive graph
drawing, in this section. They are the following:
1. The Full-Control scenario. The user has full control over the position of a new vertex
in the current drawing. The control can range from specifying lower and upper bounds
on the x and y coordinates that the new vertex will have, up to providing the exact
desired coordinates to the system. The edges can be routed by the user or by the
system.
2. The Draw-From-Scratch scenario which is based on a very simple idea: every time
a user request is posted, the new graph is drawn using one of the popular drawing
techniques. Apart from the fact that this scenario gives rather slow interactive drawing
systems, the new drawing might be completely different compared to the current one.
3. The Relative-Coordinates scenario. The general shape of the current drawing remains
the same. The coordinates of some vertices and/or edges may change by a small
constant because of the insertion of a new vertex and its incident edges (somewhere
in the middle of the current drawing), and the insertion of a constant number of rows
and columns.
4. The No-Change scenario. In this approach, the coordinates of the already placed
vertices, bends and edges do not change at all. In order to achieve such a property,
we need to maintain some invariants after each insertion.
There is a close connection between the Full-Control scenario and global routing in VLSI lay-out
[12]. The reason is that this approach deals with (re)location of vertices and (re)routing
of edges using the free space in the current drawing. The technique presented in [13] computes
routes for new edges inserted in the graph, and it does so without disturbing any of
the existing vertices and edges. The Draw-From-Scratch scenario is not interesting since
every time an update is requested by the user, the drawing system ignores all the work that
it did up to that point. The major disadvantage here is that the user has to "relearn" the
drawing.
In the rest of the paper, we discuss the other two scenaria when they are used by interactive
systems to produce orthogonal drawings of graphs. In these drawings, we assume that the
maximum degree of any vertex at any time is less than or equal to four. We also present our
results regarding the area and the number of bends that drawings under these two scenaria
require, and compare their performance.
3 The Relative-Coordinates Scenario
In this scenario, every time a new vertex is about to be inserted into the current drawing,
the system makes a decision about the coordinates of the vertex and the routing of its
incident edges. New rows and columns may be inserted anywhere in the current drawing
in order for this routing to be feasible. The coordinates of the new vertex (say v) as well
as the locations of the new rows and/or columns will depend on the following:
ffl v's degree (at the time of insertion).
ffl for each vertex u that is adjacent to v, which directions (i.e., up, down, right, or left)
around placed vertex u new edges can be inserted.
ffl Whether or not the required routing of edges can be done utilizing segments of existing
rows or columns that are free (not covered by an edge).
ffl Our optimization criteria.
When we use the Relative-Coordinates scenario in an interactive system, we can start from
an existing drawing of a graph, or we can start from scratch, that is from an empty graph.
In either case, we assume that the insertion of any vertex/edge under this scenario will not
increase the number of connected components of the current graph. The only exception to
this is when a single vertex is inserted to an empty current graph. Any other vertex inserted
during an update operation will be connected to at least one vertex of the current drawing.
Let us assume that v is the next vertex to be inserted in the current graph during an update
operation. The number of vertices in the current graph that v is connected to, is called the
local degree of v, and is denoted by local degree(v). From the discussion above it follows
that we only consider the case where an inserted vertex has local degree one, two, three or
four, except for the first vertex inserted in an empty graph. If the user wishes to insert a
new vertex that has local degree zero, then this vertex is placed in a temporary location
and it will be inserted automatically in the future, when some newer vertices increase its
(local) degree.
Assume that vertex v is about to be inserted in the current graph. For each one of the
vertices of the current drawing that is adjacent to v, the system checks the possible directions
around these vertices that new edges may be inserted or routed. The target is to minimize
the number of new rows or columns that have to open up in the current drawing, as well
as the number of bends that appear along the routed edges.
There are many different cases because there are many possible combinations. First, we
will give examples of some of the best and worst cases one might encounter, and then, we
will see in more detail how v is inserted when its local degree is one, two, three or four. In
the example shown in Fig. 1a vertices u 1 and u 2 have a free edge (i.e., grid edge not covered
by a graph edge) up and to the right respectively. In this case no new rows/columns are
needed for the insertion of vertex v and no new bends are introduced.
On the other hand however, in the example shown in Fig. 1b all four vertices
edges. The insertion of new vertex v requires the
insertion of three new rows and three new columns in the current drawing. Additionally,
eight bends are introduced. Vertices u 1 , u 2 , u 3 and u 4 have general positions in Fig. 1b,
and we can see that edge (v; u 4 ) has four bends. We can avoid the 4-bend edge, if we insert
vertex v in the way shown in Fig. 1c. The total number of new rows, columns and bends
is still the same, but the maximum number of bends per edge is now three. For a more
even distribution of the bends of the edges adjacent to vertex v, we may choose to insert it
in the way shown in Fig. 1d, where every edge has exactly two bends (three new rows and
three new columns are still required). Notice, though, that the approach described in Fig.
1d for inserting vertex v, is not always possible (e.g., we cannot have this kind of insertion
if vertices are in the same row or column).
Let v be the next vertex to be inserted. There are many cases, if one is interested in an
exhaustive analysis. However, it is relatively easy to come up with all the cases for each
insertion. Here, we distinguish the following main cases for vertex v:
1. v has local degree one. If u is the vertex of the current drawing that is adjacent to v,
we draw an edge between u and v. Edge (u; v) uses a direction (up, right, bottom, or
left) that is not taken by some other edge incident to u. This is depicted in Fig. 2a,
and this insertion requires at most either a new row or a new column. No new bend
is inserted.
2. v has local degree two. In the best case, the insertion requires no new rows, columns
or bends as shown in Fig. 1a. In the worst case, though, two new rows and one new
(a)
(b) (c) (d)

Figure

1: Insertion of v: (a) no new row or column is required, (b),(c) and (d) three new
rows and three new columns are required, with a maximum of four bends per edge in (b),
three bends per edge in (c), and two bends per edge in (d).
column, or one new row and two new columns (see Fig. 2b), and three new bends
might be required.
3. v has local degree three. In the worst case, the insertion requires a total of four new
rows and columns, and five new bends. In Fig. 2c we show an example of such an
insertion that requires one new row, three new columns and five new bends.
4. v has local degree four. The worst case requires a total of six new rows and columns;
however, at most four of them can be either rows or columns. Also, eight new bends
may be introduced, in the worst case. We have already discussed an example, which
is depicted in Fig. 1c. In Fig. 2d we show another case, where two new rows, four
new columns and eight new bends are introduced.
(b)
(a)
(c) (d)

Figure

2: Inserting v when its local degree is (a) one, (b) two, (c) three, and (d) four.
As discussed in the previous section, single edge insertions can be handled using techniques
from global routing [12] or the technique of [13]. The easiest way to handle deletions is
to delete vertices/edges from the data structures without changing the coordinates of the
rest of the drawing. Occasionaly, or on demand, the system can perform a linear-time
compaction similar to the one described in [21], and refresh the screen.
Proposition 3.1 Asssume that n vertices are inserted to a given non-empty orthogonal
drawing of a graph whose height is h and width is w, following the interactive graph drawing
scheme for the "Relative-Coordinates scenario". This insertion may add up to 8n new bends
and result in a new drawing whose area is at most ( h+w+ 3n) 2 .
Proof. Assume that all n inserted vertices have local degree four, and each one of them falls
into one of the worst cases described above, in terms of rows, columns and bends introduced.
This means that each insertion introduces eight new bends and a total of six new rows and
columns. Let h final and w final be the height and the width, respectively, of the graph after
the n vertex insertions are completed. We have that: h final 6n. The
area of the final drawing h final \Theta w final is maximized when h
3n. Hence the result follows. 2
In the rest of this section we assume that, when we use the interactive graph drawing
scheme under the Relative-Coordinates scenario, we start from scratch, that is the given
graph is empty. According to the discussion in the beginning of this section, the Relative-
Coordinates scenario guarantees that the graph that is being built is always connected after
any vertex insertion. Let n 1 denote the number of vertices of local
degree one, two, three and four, respectively, that have been inserted up to time t.
Theorem 3.1 An interactive graph drawing system under the "Relative-Coordinates sce-
nario" produces an orthogonal drawing of a connected graph, which has the following properties
at any time t:
1. after each vertex insertion, the coordinates of any vertex or bend of the current drawing
may shift by a total amount of at most 6 units along the x and y axes,
2. there are at most 3 bends along any edge of the drawing,
3. the total number of bends is at most 3n(t) \Gamma 1, and
4. the area of the drawing is at most 2:25n(t) 2 ,
where n(t) is the number of vertices that have been inserted up to time t.
Proof. The first property follows from the definition of the Relative-Coordinates scenario
and from the fact that at most six new rows and columns might open anywhere in the
current drawing (see Figs. 1b, 1c, 1d, 2d) as a result of a vertex insertion. Figures 1 and
2 cover the worst cases in terms of rows, columns and bends required for a single vertex
insertion, and for all possible local degrees of the inserted vertex. From these figures we
observe the following: First there can be at most three bends along any edge of the drawing
(see Fig. 1c). Second, the bends along an edge are introduced at the time of insertion of
the vertex that is incident to that edge.
From Figs. 1 and 2 and from the discussion above, it follows that at most 3 new bends are
introduced when a vertex of local degree two is inserted, at most 5 new bends when a vertex
of local degree three is inserted, and at most 8 new bends when a vertex of local degree
four is inserted. No new bend is introduced when a vertex of local degree one is inserted.
In other words, if B(t) is the total number of bends at time t, it holds that:
We want to compute the maximum value that B(t) can take, in order to establish an upper
bound on the number of bends of the drawing at time t. This is equivalent to solving the
following linear program:
maximize:
under the following constraints:
The first constraint is an equation on the vertices, and the second constraint is an inequality
on the edges of the graph, after n vertices have been inserted. Recall that the first vertex
to be inserted has local degree 0, since it does not have any edges yet.
Solving this linear program reveals that the maximum value of the above expression is
happens when 1. What this solution
means is that maximizing the number of bends depends solely on the number of vertices of
local degree two and four, following the insertion of the first two vertices. If we take into
account the fact that the first two vertices inserted in an empty graph have local degrees 0
and 1 respectively, what we really have is that 1. We can also see that
any other combination of values for n 2 and n 4 when n 2 +n
edges (recall that one edge is introduced by the second vertex, which has local degree 1).
From the above analysis, it follows that the upper bound on the number of bends is 3n \Gamma 1.
Regarding the area of the drawing at time t, we can infer from Figs. 1 and 2 that:
ffl when a vertex with local degree one is inserted, either a new row or a new column is
required,
ffl when a vertex with local degree two is inserted, either two new rows and one new
column are required, or one new row and two new columns are required,
ffl when a vertex with local degree three is inserted, we need a total of at most four new
rows and columns, and
ffl when a vertex with local degree four is inserted, we need a total of at most six new
rows and columns.
Let h(t) and w(t) denote the height and the width, respectively, of the drawing at time t.
Then it holds that:
since We want to maximize h(t) +w(t). If we just
multiply both sides of the last inequality (i.e., the one on the edges of the graph) by 3, we
can show that: h(t)+w(t) - 3n(t). However, this solution does not give us the values of the
variables (i.e., n 1 (t), n 2 (t), etc), for which this upper bound is achieved. For this reason,
we formulate this problem as a linear program, where the expression to be maximized is:
and the constraints are exactly the same as the ones in the above linear
program.
Solving this new linear program, we have that h(t) +w(t) is maximized when
exactly as in the linear program we studied above, for the number
of bends. According to the analysis we did for that linear program, these results really
mean that n second vertex to be inserted), 1. The
maximum value of expression 2n that we wanted to maximize is now 3n.
This means that h(t) It also holds that h(t) \Theta w(t) is maximized when
1:5n(t). In this case, the area of the drawing can be at most
Let us have a look at the expression giving the number of bends that we maximized in
the linear program of the proof of Theorem 3.1. One might be tempted to believe that
this expression is maximized when n 4 (t) is maximized (and this happens when n 4 n(t)as we will see in Lemma 4.1 of the next section). The result of the linear program was
quite revealing. We discovered that this expression is maximized only under the following
insertion sequence: insert the first two vertices with local degrees zero and one respectively,
followed by vertices of local degree two, and conclude with the insertion of exactly
one vertex of local degree four.
In Fig. 3 we show an orthogonal drawing of a graph drawn under the Relative-Coordinates
scenario we just described. This graph is regular of degree four, has 13 vertices and is
shown in Fig. 10a, together with an st-numbering for it. We insert the vertices following
the st-numbering, starting with an empty drawing. The final drawing has both height and
width equal to 9, and 20 bends. Notice that no edge has more than three bends; in fact,
there is only one edge with three bends (i.e., edge (12; 13)), whereas all the other edges have
two bends or less.
The scenario that is described in this section maintains the general shape of the current
drawing after an update (vertex/edge insertion/deletion) takes place. The coordinates of
vertices and bends of the current drawing may shift by a total amount of at most 6 units
along the x and y axes, as a result of an update operation. This change does not affect the
number of bends of the current drawing even if the update operation is a vertex insertion.
This scenario works well when we build a graph from scratch, or we are presented with a
drawing (which was produced somehow, perhaps by a different system) and we want our
interactive system to update it. In order to refresh the drawing after each update, the
coordinates of every vertex/bend affected must be recalculated. Hence, it would take linear
Figure

3: An orthogonal drawing of a regular, degree four, 13-vertex graph, under the
Relative-Coordinates scenario.
4 The No-Change Scenario
In this scenario, the drawing system never changes the positions of vertices and bends of
the current drawing. It just increments the drawing by adding the new elements. This is
useful in many cases where the user has already spent a lot of time studying a particular
drawing and he/she does not want to have to deal with something completely different after
each update.
Papakostas and Tollis [17] defined this scenario and presented some preliminary results
on it. No other work is known that gives satisfactory answers to the above described
scenario. In this section we present a simple yet effective scheme for allowing the insertion
of vertices, under the No-Change scenario. As in the previous scenario, our scheme produces
an orthogonal drawing under the assumption that the maximum degree of any vertex at
any time is less than or equal to four.
In the description of our interactive graph drawing scheme, we assume that we build a graph
from scratch. If a whole subgraph needs to be drawn initially, we can draw it by simulating
the above scenario, inserting one vertex at a time. We assume that the graph is always
connected. In the following section, we present an extension of the No-Change scenario,
allowing the current graph to have more than one connected component at any time.
Let u be a vertex of the current drawing, and let v be the next vertex to be inserted. There
are four possible ways that vertex u can be connected to vertex v, so that there is an edge
(u; v) in the new drawing (see Fig. 4a). Each one of these ways is a free direction of vertex
u. Vertex u may have up to two free directions to the right (through edges e 1 and e 2 of
Fig. 4a), and up to two free directions to the bottom (through edges e 3 and e 4 of Fig. 4a).
Vertex u has a free direction to the right if and only if there is no edge of the current graph
using the portion of u's row to the right of u and the portion of u's column to the top of
u. Similarly, we can define u's free direction to the bottom. Vertex u's free direction to the
right (bottom) through edge e 2 (e 3 ) is called bend-free (see Fig. 4a).
When vertex v is inserted, it is connected to some vertices that have already been placed.
The local degree of a vertex that is about to be inserted to the current drawing is defined in
the same way as in the scenario studied in the previous section. Since the graph is always
connected, we only consider the case where an inserted vertex has local degree one, two,
three or four, except for the first vertex inserted in an empty graph. If a new vertex has
local degree zero, then it is placed in a temporary location and it will be inserted in the
future, when some newer vertices increase its (local) degree. In order to prove our results,
we maintain the following invariants as vertices are inserted in the drawing:
ffl Every vertex of the current drawing of degree one has either two free directions to
the bottom and a bend-free one to the right, or two free directions to the right and a
bend-free one to the bottom of the grid point where the vertex is placed.
ffl Every vertex of the current drawing of degree two has either one free direction to the
bottom and one to the right, or two free directions to the right, or two free directions
to the bottom of the grid point where the vertex is placed.
ffl Every vertex of the current drawing of degree three has a free direction either to the
bottom or to the right of the grid point where the vertex is placed.
Figures 4b and 4c show the first two vertices inserted in an empty graph. Notice that
after vertices v 1 and v 2 are inserted, they both satisfy the invariants set above. Different
placements of the first two vertices are possible but the edge that connects them always has
to have one bend in the way shown in Fig. 4c. If a straight no-bend line is used to connect
at least one of these two vertices will not satisfy the first invariant.
(a) (b) (c)

Figure

4: (a) Possible free directions of a vertex u of the current drawing, (b),(c) inserting
the first two vertices in an empty graph.
Let us assume that v i is the next vertex to be inserted in the current drawing. We distinguish
the following cases:
(a) (b)

Figure

5: Insertion of local degree one vertex v i requires at most one column and one row.
(b)
(a)

Figure

(a) Insertion of local degree two vertex v i requires one column, (b) insertion of v i
now requires one column and one row.
1. v i has local degree one. There are two cases which are shown in Figs. 5a and 5b.
At most one new column and one new row are required, and at most one bend is
introduced. Notice that this bend is introduced along an edge which is incident to
whose other end is open. In Fig. 5a the vertex will have one free direction
to the bottom and two to the right. The second free direction to the right (which is
responsible for introducing an extra row and bend to the drawing) will be inserted in
the drawing later and only if v i turns out to be a full blown degree four vertex. We
take a similar approach for the second downward free direction of v i of Fig. 5b.
2. v i has local degree two. There are four cases. We have shown two cases in Figs. 6a and
6b (the other two are symmetric and are treated in a similar fashion). At most one new
row and one new column is required, and at most two bends are introduced. Notice
that these bends are introduced along edges which are incident to v i and connect v i
with the current drawing.
3. v i has local degree three. There are eight cases. All cases, however, can be treated by
considering just two cases, as shown in Fig. 7: (a) all the vertices have a free direction
to the right (bottom), and (b) two vertices have a free direction to the right (bottom)
and the other vertex has a free direction to the bottom (right). The rest of the cases
are symmetric and are treated in a similar fashion. At most one new row and one
new column are required, and at most three bends are introduced. Notice that these
bends are introduced along edges which are incident to v i and connect v i with the
current drawing.
4. v i has local degree four. There are sixteen cases. All cases, however, can be treated
by considering just three cases, as shown in Fig. 8: (a) all the vertices have a free
direction to the right (bottom), (b) three vertices have a free direction to the right
(bottom) and one vertex has a free direction to the bottom (right), and (c) two
vertices have a free direction to the right (bottom) and the other two vertices have
direction to the bottom (right). The symmetric cases are treated in a similar
fashion. At most two new rows and two new columns are required, and at most six
bends are introduced. Notice that these bends are introduced along edges which are
incident to v i and connect v i with the current drawing.
As we described above, the easiest way to handle deletions is to delete vertices/edges from
the data structures without changing the coordinates of the rest of the drawing. Occasionaly,
(a) (b)

Figure

7: (a) Insertion of local degree three vertex v i requires one column, (b) insertion of
now requires one row and one column.u
(c)
(b)
(a)

Figure

8: (a) Insertion of local degree four vertex v i requires two columns, (b) insertion of
requires two columns and one row, (c) insertion of v i requires two columns and two rows.
or on demand, the system can perform a linear-time compaction similar to the one described
in [21], and refresh the screen.
Lemma 4.1 The total number of bends introduced by an interactive graph drawing system
under the "No-Change scenario" up to time t is at most 2:66n(t) is the
number of vertices at time t. This upper bound is tight.
Proof. Vertex v 1 is the first vertex to be inserted into an empty drawing and is also the
only vertex that has local degree zero (see Fig. 4b). The insertion of v 1 contributes (or will
contribute) at most two bends: The first one is along edge (v the second one will be
along direction to the right which is not bend-free (see Fig. 4c), if v 1 turns out to
be a degree four vertex. Let v i be the next vertex to be inserted in the drawing. If v i has
local degree one, two or three, then its insertion introduces at most one, two or three bends,
respectively, as depicted in Figs. 5, 6 and 7. If v i has local degree four, then its insertion
introduces at most six bends as shown in Fig. 8.
Let B(t) denote the total number of bends at time t. Then we have the following expression
for
is the graph that has
been drawn up to time t, and n 4 (t) is the number of vertices of local degree four which have
been inserted up to time t.
It follows that B(t) - 2n(t) 2. In order to establish an upper bound for B(t) we
need to compute the maximum number of vertices of local degree four that can be inserted
up to time t under any insertion sequence. Let 4n 4 (t) be the number of edges of the drawing
which were contributed by all n 4 (t) vertices of local degree four up to time t. Let m 0 be the
number of the rest of the edges of the drawing at time t. It holds that
Notice that n 4 (t) is maximized when m 0 is minimized. Since the graph that has been drawn
up to time t has to be connected, it holds that From that, it follows that
the maximum value for n 4 (t) is n(t)Recall that the number of bends at time t, is B(t) - 2n(t) after the
hence the result follows.
To show the tightness of this upper bound, we build the drawing of a graph with 6 vertices
under the No-Change scenario, in the following way: First, we insert vertices 1 and 2 in the
way shown in Fig. 4c. Next, we insert vertex 3 which is adjacent to vertex 2, and then we
insert vertex 4 which is adjacent to vertices 1 and 3 of the current drawing. In the last two
steps, we insert vertices 5 and 6 of local degree four, so that each one is adjacent to vertices
4. The final drawing is shown in Fig. 9b. We use dotted boxes to denote the
current drawing at each intermediate step. Counting the number of bends of the drawing
reveals that this number is 2. 2
Theorem 4.1 An interactive graph drawing system under the "No-Change scenario" produces
an orthogonal drawing of a connected graph, which has the following properties at any
time t:
1. every insertion operation takes constant time,
2. every edge has at most three bends,
3. the total number of bends at any time t is at most 2:66n(t) is the
number of vertices of the drawing at time t,
4. the area of the drawing at any time t is no more than (n(t)
is the number of vertices of local degree four which have been inserted up
to time t, and
5. the upper bounds for both area and bends are tight.
Proof. Part 1 follows easily from the description we gave above regarding the insertion
of individual vertices. For Part 2, notice that each newly inserted vertex v i adds at most
bends along its incident edges (see Figs. 5, 6, 7 and 8). It is possible that an incident
edge e of v i might have already had one bend if the vertex of the current drawing which
is connected to v i through e (say u) was inserted as a local degree one vertex. This is also
illustrated in Fig. 9a. From Lemma 4.1 it follows that the number of bends of the drawing
at time t can be at most 2:66n(t) + 2. In the same lemma we discussed the tightness of this
upper bound.
Let us assume that vertex v 1 is the first vertex to be inserted to an empty drawing (see
Fig. 4b). Vertex v 1 is the only vertex of local degree zero inserted to the drawing. The
insertion of vertex v 1 may introduce a total of two new rows and two new columns, if v 1
turns out to be a vertex of degree four. This can be seen in Fig. 4c, where v 1 requires
one row and one column to place itself, and one additional row and column for its two
directions which are not bend-free. From this and the discussion above, we have that
the maximum width or height of the drawing at time t cannot be more than 2
are the number of vertices of local
degree one, two and three, respectively, which have been inserted up to time t. Notice that
From the proof of Lemma 4.1 we have that
the absolute maximum value that n 4 (t) may take under any circumstances is: n(t). So, the
area is at hence the result follows.
Finally, the drawing of Fig. 9b demonstrates not only the tightness of the upper bound on
the number bends (see proof of Lemma 4.1), but also the tightness of the upper bound on
the area discussed in the last paragraph. Notice that the area of the drawing is (8 \Theta
squared units, and this is equal to d1:77 \Theta 6 2 e. 2
(a) (b)

Figure

9: (a) At most 3 bends may appear along any edge e of the drawing, (b) a drawing
under the No-Change scenario demonstrating the tightness of the upper bound on area and
number of bends.
The interactive scheme we just described is simple and efficient. The area and bend bounds
are higher than the best known [1, 2, 15, 16]. However, we have to consider that this is a
scheme that gives the user a lot of flexibility in inserting any node at any time. Moreover,
any insertion takes place without disturbing the current drawing, since the insertion is built
around it. Furthermore, n 4 (t) is the number of vertices of local degree four which have been
inserted up to time t, and not the total number of vertices of degree four in the graph. The
area will be smaller if the user chooses an insertion strategy which keeps n 4 (t) low.
Notice that it is possible to reuse rows and columns on which other vertices have been
placed before. Although we cannot guarantee that this will always happen, the interactive
drawing program should be able to see if a reuse is possible during an insertion, and take
advantage of it.
In Fig. 10 we show an example of our technique when applied on a regular graph of degree
four that has 13 vertices. The graph, along with an st-numbering is shown in Fig. 10a. We
simulate the interactive technique we introduced above for the No-Change scenario and we
insert the vertices following the st-numbering, starting with an empty drawing. The final
drawing has width 10, height 11, 24 bends, and is demonstrated in Fig. 10b. Note that the
dotted boxes denote the current drawing at all intermediate steps, and we can see that it
always remains unaltered. Also notice that when vertex 9 was inserted, we reused vertex
2's column.
(a)
(b)36
Figure

10: (a) A regular graph of degree 4 with 13 vertices, (b) drawing the graph under
the No-Change scenario.
5 Comparisons and Extensions
From the analyses of the Relative-Coordinates and No-Change scenaria which we presented
in the previous sections, we can conlcude that the worst-case performance of the No-Change
scenario is better than that of the Relative-Coordinates scenario in terms of the area and
the number of bends of the drawings that they produce. More precicely, an interactive
graph drawing system under the No-Change scenario produces an orthogonal drawing
ffl less area, and
ffl smaller total number of bends
than the orthogonal drawing of the same graph produced by an interactive drawing system
under the Relative-Coordinates scenario.
Note that this comparison is a worst-case comparison. It holds when both systems draw a
graph from scratch (i.e., the very first update operation applies on an empty graph), and
when the drawn graph is connected at all times. Another advantage of the No-Change
scenario is that each update operation takes constant time, since the coordinates of vertices
and bends of the current drawing are never altered. In the case of the Relative-Coordinates
scenario, re-drawing the whole graph after an update operation requires linear time since
the coordinates of many vertices and bends of the current graph may be shifted (by a total
amount of at most 6 units along the two axes). Note that if the user does not wish to
produce a drawing of the graph after an update operation, then the operation itself takes
constant time, since the data structures of the graph can be updated in constant time.
However, the Relative-Coordinates scenario has one important feature: it gives the user the
ability to insert a vertex into any orthogonal drawing (of degree four), at any time. This
results from the fact that no invariants are maintained while drawing under this scenario.
The Relative-Coordinates scenario offers a lot of flexibility at a very small cost: the coordinates
of vertices and bends of the current drawing may be shifted by a small amount,
as a result of an update operation, and re-drawing of the graph may be required. It is
important to underline, though, that the shift of coordinates affects all vertices and bends
of the current drawing in the same relative way. Hence, the general shape of the current
drawing is still maintained after the update operation is complete.
In the rest of this section we extend both the Relative-Coordinates and the No-Change
scenaria to the case where the current graph is allowed to become disconnected during the
interactive drawing process. In other words, inserting more than one vertices of local degree
zero (i.e., vertices that are not adjacent to any other vertex at the time of their insertion)
is now allowed. The other characteristics of the drawing remain unchanged, that is we
assume that the drawing is orthogonal with maximum degree four, and we start the update
operations with an originally empty graph.
Theorem 5.1 An interactive graph drawing system under the "Relative-Coordinates sce-
nario" produces an orthogonal drawing of a graph, which has the following properties at any
time t:
1. after each vertex insertion, the coordinates of any vertex or bend of the current drawing
may shift by a combined of at most 6 units along the x and y axes,
2. there are at most 3 bends along any edge of the drawing,
3. the total number of bends is at most 4n(t), and
4. the area of the drawing is at most 3n(t) 2 ,
where n(t) is the number of vertices that have been inserted up to time t.
Proof. The first two parts of the theorem come directly from Theorem 3.1. Regarding the
total number of bends at time t, it still holds that:
since the insertion of vertices of local degree zero introduces no bends (see also the proof
of Theorem 3.1). Linear programming is employed once again to compute the maximum
value that B(t) can take, which is an upper bound on the number of bends of the drawing
at time t. The new linear program is the following:
maximize:
under the following constraints:
The first constraint is an equation on the vertices, and the second constraint is an equation
on the edges of the graph, after n vertices have been inserted. Note that n 0 is the number
of vertices of local degree zero; these vertices do not contribute any edges to the drawing.
Solving this linear program reveals that the above expression is maximized when
maximum is equal to 4n.
Let h(t) and w(t) denote the height and the width, respectively, of the drawing at time
t. Vertices of local degree zero open up either a new row or a new column. Vertices of
local degree one, two, three or four follow the rules described in the proof of Theorem 3.1,
regarding the number of rows or columns that they open up. It holds that:
h(t)
since We want to maximize h(t) +w(t). As above,
this problem can be formulated as a linear program, where the expression to be maximized
is: and the constraints are exactly the same as the ones in the
above linear program.
Solving this new linear program, we have that h(t) + w(t) is maximized when
exactly as in the linear program we studied above, for the
number of bends. The maximum value of the expression is equal to 3:5n, which means that
It also holds that h(t) \Theta w(t) is maximized when
h(t)+w(t)
1:75n(t). In this case, the area of the drawing can be at most 3n(t) 2 . 2
We now extend the No-Change scenario to the case where the current graph is allowed to
become disconnected during the interactive drawing process. When a vertex of local degree
zero is inserted, we either open up a new column and place it to the right of a bend of the
current drawing (thus reusing a row), or open up a new row and place it to the bottom of
a bend of the current drawing (thus reusing a column). If neither of the two is possible,
we open up one new row and one new column to place the local degree zero vertex. Note
that a vertex of local degree zero may later contribute one more row and one more column
to the drawing, if it uses its free directions which are not bend-free (see Fig. 4a). In this
case, the vertex of local degree zero will be connected to four other vertices. As above, n i (t)
denotes the number of vertices of local degree i which have been inserted
up to time t. The following theorem holds:
Theorem 5.2 An interactive graph drawing system under the "No-Change scenario" produces
an orthogonal drawing of a graph, which has the following properties at any time
t:
1. every insertion operation takes constant time,
2. every edge has at most three bends,
3. the total number of bends at any time t is at most 4n(t), where n(t) is the number of
vertices of the drawing at time t, and
4. the area of the drawing at any time t is at most 4n(t) 2 .
Proof. The first two parts come directly from Theorem 4.1. Following the proof technique
of Lemma 4.1 for the total number of bends B(t) at time t, we have that: B(t) - 2n
2n 4 (t)+2n 0 (t). Recall that each vertex of local degree zero can contribute up to two bends,
if it is connected to four vertices at time t (see description of the No-Change scenario in
previous section). If n(t) is the total number of vertices that have been inserted up to time
t, then the maximum value that n 4 (t) can take is: n(t)(similar to the proof of Lemma 4.1
by replacing m 0 with 0 since the graph may be disconnected at any intermediate moment).
This means that n 0 (t) can be at most n(t), so the total number of bends is no more than
4n(t) at time t.
A vertex of local degree zero may open up at most two new rows and two new columns, if it is
connected to four vertices at time t. Vertices of local degree one, two, three or four follow the
rules described in Section 4, regarding the number of new rows and columns that they open
up, for the No-Change scenario. From this, it follows that the maximum width or height of
the drawing at time t is at most 2n 0 (t)+n 1 (t)+n 2 (t)+n 3 (t)+2n 4
can now be up to n(t)each, the area is at most 4n(t) 2 . 2
The upper bounds on the number of bends and area change, when we extend the two
scenaria to the case where the graph can become disconnected during the drawing process.
Notice that the Relative-Coordinates scenario has now a better worst-case behavior than
the No-Change scenario, with respect to the area that the drawing requires. As far as the
number of bends is concerned, we have a tie, since both scenaria depict an upper bound
equal to 4n(t).
It is also worth noting that vertices of local degree zero and four play the most major
role in the worst-case behavior of the Relative-Coordinates scenario, in terms of both the
area and the number of bends. In fact, based on the results of the two linear programs
discussed above, the upper bound expressions for the area and the number of bends were
maximized, when the total number of vertices inserted is split between these two kinds of
vertices. Recall that, when the graph has to be connected at all times, it is the vertices
of local degree two, that play the most important part in the worst-case behavior of the
Relative-Coordinates scenario (see proof of Theorem 3.1).
6 Conclusion and Future Work
In this paper we discussed some possible scenaria for an interactive orthogonal graph drawing
system. We used linear programming as an upper bound technique to analyze the
performance of the Relative-Coordinates scenario. We also analyzed the No-Change scenario
and compared the two scenaria. Our results focus on the following aspects of the
produced drawings, or the drawing process:
ffl area,
ffl number of bends (per edge and total),
ffl tightness of upper bounds,
ffl extent to which the drawing changes after an update operation, and
time to complete an update operation.
An important property of an interactive graph drawing system is to introduce the minimum
possible change to a drawing (that is preserve the user's ``mental map''), after each update
operation. The No-Change scenario guarantees that the current drawing is never altered
since any vertex insertion and edge routing takes place around it. On the other hand,
the Relative-Coordinates scenario typically requires a small change in the coordinates of
vertices and bends of the current drawing. However, the general shape of the drawing
is maintained after each update operation. The worst-case performance bounds of the
No-Change scenario, in terms of area and bends, are better than the corresponding bounds
obtained by the Relative-Coordinates scenario (if the drawn graph is at all times connected).
However, the Relative-Coordinates scenario is less restrictive, since it does not maintain any
invariants when it produces a new drawing.
In [14] three different models are proposed to capture the notion of the user's "mental
map" of a drawing. Although our work was developed independently of the work in [14]
and addresses different problems, it turns out that our scenaria follow some of their models.
ffl the Relative-Coordinates scenario preserves the user's mental map in terms of the
orthogonal ordering model of [14], and
ffl the No-Change scenario preserves the user's mental map in terms of both the orthogonal
ordering and proximity models of [14].
We have implemented the two scenaria (i.e., Relative-Coordinates and No-Change) and
conducted a preliminary experimental study comparing their performance on a data set
containing over 8000 graphs of maximum degree four. Our experiments mainly focus on
measuring the area and the total number of bends that the two scenaria require for the
graphs of our data set. Our preliminary results indicate that:
ffl The Relative-Coordinates scenario always exhibited better performance than No-Change
in terms of both area and number of bends.
ffl The practical behavior of the two scenaria was much better than their established
theoretical worst-case bounds, in most cases. In other words, the worst case did not
happen very frequently.
An extensive description of our experimental results along with heuristics on the placement
of vertices will appear in a forthcoming paper.
It is an interesting open problem to develop a theory that enables the insertion, move or
deletion of more than one vertices simultaneously (that is a block of vertices) in the current
drawing, efficiently. The area of interactive graph drawing will grow in the next years
because of the many applications that demand it. Techniques for interactive graph drawing
in other standards (straight line, polyline, etc.) are needed, and should be explored. Since
it is counterproductive for the user to spend a significant amount of time to "relearn" the
new drawing, the main target is to produce a drawing that is as close to the drawing before
the update as possible.

Acknowledgement

We would like to thank Brendan Madden and Roberto Tamassia for helpful discussions.



--R

Embedding Nonplanar Graphs in the Rectangular Grid
A Better Heuristic for Orthogonal Graph Drawings
Dynamic Graph Drawing
Algorithms for Drawing Graphs: An Annotated Bibliography
Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs
Rectilinear Planar Drawings with Few Bends in Each Edge
Computing an st-numbering
On the Computational Complexity of Upward and Rectilinear Planarity Testing
Drawing planar graphs using the lmc-ordering
New lower bound techniques for VLSI

Combinatorial Algorithms for Integrated Circuit Layout
An Incremental Approach to Aesthetic Graph Layout
Layout Adjustment and the Mental Map
Algorithms for Area-Efficient Orthogonal Drawings
Improved Algorithms and Bounds for Orthogonal Draw- ings
Issues in Interactive Orthogonal Graph Drawing
Drawing Graphs on Rectangular Grids
On minimal node-cost planar embeddings
On embedding a graph in the grid with the minimum number of bends
Planar Grid Embeddings in Linear Time
Lower Bounds for Planar Orthogonal Drawings of Graphs
Universality Considerations in VLSI Circuits
--TR

--CTR
Janet M. Six , Ioannis G. Tollis, Effective Graph Visualization Via Node Grouping, Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS'01), p.51, October 22-23, 2001
graphical user interface;orthogonal graph drawing;interactive orthogonal graph drawing;information visualization;graph drawing