Removing Node Overlapping in Graph Layout Using Constrained Optimization.
Although graph drawing has been extensively studied, little attention has been paid to the problem of node overlapping. The problem arises because almost all existing graph layout algorithms assume that nodes are points. In practice, however, nodes may be labelled, and these labels may overlap. Here we investigate how such node overlapping can be removed in a subsequent layout adjustment phase. We propose four different approaches for removing node overlapping, all of which are based on constrained optimization techniques. The first is the simplest. It performs the minimal linear scaling which will remove node-overlapping. The second approach relies on formulating the node overlapping problem as a convex quadratic programming problem, which can then be solved by any quadratic solver. The disadvantage is that, since constraints must be linear, the node overlapping constraints cannot be expressed directly, but must be strengthened to obtain a linear constraint strong enough to ensure no node overlapping. The third and fourth approaches are based on local search methods. The third is an adaptation of the EGENET solver originally designed for solving general constraint satisfaction problems, while the fourth approach is a form of Lagrangian multiplier method, a well-known optimization technique used in operations research. Both the third and fourth method are able to handle the node overlapping constraints directly, and thus may potentially find better solutions. Their disadvantage is that no efficient global optimization methods are available for such problems, and hence we must accept a local minimum. We illustrate all of the above methods on a series of layout adjustment problems.
Introduction
Graph drawing has been extensively studied over the last fteen years. However,
almost all research has dealt with graph layout in which the nodes are treated as
points in the layout of graphs. Unfortunately, treating nodes as points is inadequate
for many applications. For example, a textual label is frequently added to
each node to explain some important information, as in many illustrative diagrams
for engineering designs, the human body and the geography, and even a satisfactory
layout for a point-based graph may lead to node overlapping when labels are
considered. For this reason, we are interested in layout adjustment which takes an
initial graph layout with the sizes of the nodes as inputs, and then modies the
original graph layout so that node overlapping is removed.
We primarily address the problem of layout adjustment in a dynamic context.
This is useful in interactive applications such as graph display in which sub-graphs
are enlarged and shrunk or node labels are changed. Here the aim is take an existing
graph layout and remove node overlapping while preserving the user's mental map
of the graph. Following, Misue et al [17] in order to minimize change to the mental
map we preserve the graph's orthogonal ordering, that is to say, the relative ordering
of the nodes in both the x and y direction, and attempt to place nodes as closely
as possible to their original positions. We also consider layout adjustment in the
context of a static graph. In this case we wish to minimize the area of the graph
in the new layout. However, since we assume that some sophisticated graph layout
algorithm has been used to give an initial layout for the graph, like the dynamic
case we still try to preserve the initial layout while removing node overlapping.
In this paper we study four dierent proposals for performing graph layout adjust-
ment. All approaches model the problem as a constrained optimization problem.
An advantage of viewing layout adjustment as a constrained optimization problem
is that we can also add constraints which capture the semantics of the diagram if it
is not just a simple graph. For example, we can add constraints which specify that
certain nodes must be on the boundary of the graph or which specify the relative
placement of nodes.
Our rst approach to layout adjustment is the simplest. It performs the minimum
linear scaling in both the x and y directions which will remove node-overlapping.
We give a simple and e-cient algorithm based on dynamic programming for nding
this minimum. The disadvantage is that uniform scaling means that nodes are often
moved unnecessarily far, and so this approach may not lead to good layout.
The second approach is based on formulating the node overlapping problem as a
convex quadratic programming problem which can then be solved using a quadratic
solver. This approach is attractive because algorithms for convex quadratic optimization
are well understood, and global optimization is possible in polynomial-
time. The main disadvantage arises from the need to model node overlapping
constraints using linear constraints. Unfortunately, the no node-label overlap constraint
between nodes u and v is inherently disjunctive, i.e. u is su-ciently to the
left of v or u is su-ciently above v or u is su-ciently to the right of v or u is
su-ciently below v. This cannot be expressed directly but must be strengthened
to obtain a linear constraint strong enough to ensure no node overlapping. Optimal
layout with respect to this stronger linear constraint may be sup-optimal with
respect to the original no node-label overlap constraints.
In contrast the third and fourth approaches allow the disjunctive node overlapping
constraint to be expressed directly. Both approaches use local search methods [1,
2, 7, 6, 27]. A local search method starts with a current value for each variable, and
by examining the local neighbourhood tries to move to a point which is closer to the
optimum. Constraints are handled as penalties to the optimization function. The
search proceeds until a local minimum is found. When the local minimum represents
a solution (all constraints are satised), the algorithm terminates. Otherwise, it
may penalize this local minimum to avoid visiting it again, and then continue the
search until it nds a solution. Because for layout adjustment problems we have a
starting position \close" to the global optimum, namely the initial layout, in many
cases local search can e-ciently nd the optimum.
The third approach is a modication of the EGENET [11] solver (an extension
of the GENET model [27]) to perform layout adjustment. Modications are required
to (a) handle a constraint optimization problem (as opposed to constraint
satisfaction for which EGENET is designed) and (b) to handle real (
oating point)
variables, rather than variables with a discrete domain. Our work represents the
rst attempt, that we know of, to investigate how the EGENET solver can be used
to solve constrained optimization problems involving real numbers 1 .
Our fourth approach is an adaptation of the Lagrangian multiplier methods
(LMMs) [13, 20, 26], a classical optimization technique used in operations research.
Lagrangian multiplier methods are a general approach to constrained optimization
which have been applied to many di-cult problems successfully. Here we develop a
specic Lagrangian algorithm where variables are treated in pairs corresponding to
node positions. Because of the non-convexity of the constraints, we repeatedly optimize
using the results of the previous optimization to give a new, possibly better,
starting position for the search.
There has been little work on layout adjustment and mental map preservation.
The most closely related papers are that of Eades et al [9] in which mental map
was proposed for the rst time and orthogonal ordering, proximity relations and
topology were given as three criteria, and that of Misue et al [17], which provides a
force-directed algorithm called the force scan algorithm to perform dynamic graph
layout adjustment. We demonstrate that our methods, apart from the uniform
scaling approach, give better layout than the force scan algorithm, although they
are slower.
Other related work includes Lyons [15] who tries to improve the distribution of the
nodes in the new layout according to some measures of distribution (cluster busting)
while simultaneously trying to minimize the dierence between the two layouts according
to some measures of dierence (anchored graph drawing). Eades et al [8] try
to preserve the mental map in animated graph drawing by using a modied spring
algorithm to provide smooth user transitions. Other related work includes: [19],
[4], [14], [18] and [21]. A preliminary version of our second proposal, including a
proof, appeared in [10]. For a comprehensive survey of graph drawing methods,
see [3, 22].
Finally we mention some previous work [24, 25] on adapting the GENET model
to solve constraint optimization problems [23]. Guided Local Search (GLS) [25]
iteratively calls a local search procedure, based on the GENET variable updating
scheme, to modify and minimize an augmented cost function until a predened
stopping condition is reached. GLS had been successful in solving Radio Link
Frequency Assignment Problems.
This paper is organized as follows. In Section 2 we describe how to view the lay-out
adjustment problem as a constrained optimization problem and introduce both
a static and dynamic version of the problem. In Section 3 we describe the simplest
approach to solving the layout adjustment problem, linear scaling. In Section 4 we
show how to replace the disjunctive no-node overlapping constraints of the layout
problem with linear approximations. This allows us to transform the layout adjustment
problem to a quadratic programming problem, which can then be handled
by any quadratic solver. In Section 5 we introduce the original EGENET model.
Then, we discuss how to modify the EGENET model to handle both the static
and dynamic layout problems as continuous constrained optimization problems. In
Section 6 we brie
y describe some basic concepts in multiplier methods, and then
discuss how to adapt these concepts to derive a Lagrangian-based search procedure
specialized for layout adjustment problems. We provide an empirical evaluation of
our four proposals using a set of arbitrary graph layout problems investigating both
their e-ciency and eectiveness in Section 7. We also compare our approaches to
the force-scan algorithm of Misue et al. Finally, we summarize and conclude our
work in Section 8.
2. Layout Adjustment as Constrained Optimization
All our algorithms for layout adjustment are based on translating the problem into
a constrained quadratic optimization problem of the form
minimize  with respect to C
where  is a quadratic expression and C is a (possibly non-linear) collection of
constraints. All are in terms of variables representing the position of each node.
We assume that we are given
A (possibly directed) graph ng is the set of nodes
in the graph, and E  V  V is the set of edges in the graph, that is to say,
there is a edge from node u to node v.
A node labelling for G which consists of two vectors wn ) and
each node v to the width (w v ) and height (h v ) of
its label respectively.
And an initial layout for the graph G, which consists of two vectors, x
n ) which map each node v to its x or y position
respectively. That is to say, node v is placed at
Intuitively, as shown in Figure 1, each node has a rectangular bounding box and
the display area has origin at its lower left corner with x axis rightwards and y
upwards.
The variables of the layout adjustment problem are the x and y coordinates of the
nodes, which we shall represent using two vectors x and y. The constraints on the
problem for layout adjustment must ensure that there is no node overlapping in the
resulting solution. These constraints (C no ) can be expressed as: for all u;
Y

Figure

1. Notation
(v to the right of u)
to the right of v)
or equivalently
In fact, we usually want the nodes to be separated by some minimum distance d
and not directly abutt each other. This is simply handled by modifying the height
and width of each node by adding the distance d, and treating the problem as no
overlap of these new larger nodes.
As indicated in the introduction, we are primarily concerned with layout adjustment
in the context of dynamic graph layout. This is useful in interactive
applications such as graph display in which sub-graphs are enlarged and shrunk or
node labels are changed. Here the aim is take an existing graph layout and remove
node overlapping while preserving the user's mental map of the graph.
One heuristic to ensure that the aesthetic criteria remain satised and that the
new layout is \similar" to the initial layout is to preserve the orthogonal ordering
of the original layout [17]. The idea is to preserve the relative ordering of the nodes
in the x and y directions. In our context, linear constraints (C oo ) which ensure the
preservation of orthogonal ordering are: for each u;
v then
x u < x v
and if x 0
v then
x
and similarly for the y-direction. We shall use this heuristic for our rst two
approaches|uniform scaling and quadratic programming|but not for the local
search based methods.
The dynamic layout adjustment problem is to nd a new layout for G, x and y,
so that the constraints C are satised and the position of each node is as close as
possible to its original position. We encode the dynamic layout adjustment problem
as a constrained optimization problem by setting the objective function  dyn to be,
and we wish to
minimize  dyn subject to C (1)
where we can choose the constraints of the problem C to be either C no or C no ^C oo .
The new layout is given by an optimal solution to the above problem.
Apart from layout adjustment in a dynamic context, we might also consider layout
adjustment in a static context. In this case the underlying assumption is that the
initial layout has been generated using some sophisticated graph layout algorithm
which captures aesthetic criteria. We do not want to redo this work in the layout
adjustment phase. Hence, static layout adjustment should remove node-label overlapping
but still preserve the (presumably) aesthetically pleasing node placement of
the initial layout. We are also interested in minimizing the overall area of the graph.
Preserving the initial layout is very similar to preserving the user's mental model,
and so we can use the same techniques: constraints to preserve orthogonal ordering
and a term in the objective function to move nodes as little as possible. The
main dierence to the dynamic layout adjustment problem is an extra term in the
objective function,  stat , which allows the area of the new layout to be minimized.
More precisely, the static layout adjustment problem is to nd a new layout for
G, x and y, by solving the constrained optimization problem
subject to C (2)
where C is either C no or C no ^ C oo , k  0 is a weighting factor and
and towards which the layout is supposed to be shrunk.
can be the arithmetical average of all nodes' x (y) coordinates, or median of
all nodes' x (y) coordinates. One can also take the position of centroid of a graph
or even a predened point as c. Minimization will attempt to place the nodes as
close as possible to a predened position, so reducing the overall area of the new
layout.
Despite its dierent motivation, the formulation of the static layout adjustment
problem is very similar to that for the static. Thus, in the following sections, we
will focus on techniques for solving the dynamic case since they can also be used
with little modication to solve the static case.
3. Using Uniform Scaling
We rst consider a very simple approach to layout adjustment in which we uniformly
scale the graph to remove overlapping. We nd c x , m x , c y and m y and move each
node
v ) to (m x x 0
this is a linear transformation,
it preserves the graph's orthogonal ordering (indeed, all of the original graph's
structure) and the scaling factors m x and m y are chosen so that node overlapping
is removed. The disadvantage is that uniform scaling may cause nodes to move
unnecessarily.
We rst examine how to compute c x and c y for given scaling factors m x and m y .
It follows from Equation 1 that we must minimize  scale where this is
This is minimized when
where  x and  y are the means of the x 0
v 's and y 0
's, respectively. It follows that
x and  2
y are the variances of the x 0
v 's and y 0
's, respectively.
Now we consider how to compute the scaling factors. Consider node
dimensions (w dimensions (w
similarly for my ij . By construction mx ij is
the minimum amount of scaling in the x direction which will remove the overlap
between the two nodes and similarly mx ij is the minimum amount of scaling in the
y direction to remove this overlap.
Hence we can solve the layout adjustment problem using scaling by nding scale
factors sx and sy that solve the constrained optimization problem:
minimize  scale subject to 81  i <
Inspection of Equation 4 reveals that we should choose the minimal scaling factors
removes overlapping. This means that m x will be mx ij
for some overlapping nodes i and j and similarly for m y .
This observation leads to the algorithm shown in Figure 2. It computes c x ,
which remove all overlapping (if possible) and which minimize
layout-scale
compute the mean mu x and variance  2
x of the x 0
's
compute the mean mu y and variance  2
y of the y 0
's
lexicographically into the array a[1:::m]
let a[k] have form (mx
/* compute possible pairs of scaling factors bmx[k] and bmy[k] */
endfor
/* now determine which pair has least cost */
bestcost
cost
y
if (cost < bestcost) then
bestcost := cost
best := k
endif
endfor
solution
else m x := bmx[best]

Figure

2. Scaling method for layout adjustment
scale . The only subtlety to notice is that, for each i, the scaling factors bmx[i] and
bmy[i] remove all overlapping since scaling by bmx[i] in the x-dimension removes the
overlapping corresponding to a[1]; :::; a[i] and scaling by bmy[i] in the y-dimension
removes the overlapping corresponding to a[i
The main part of the algorithm has complexity O(m log m) where m is the number
of overlapping nodes. Since the number of overlapping nodes is O(jV j 2 ), the overall
complexity is O(jV j 2 log jV j).
4. Using Quadratic Programming
Quadratic programming is used to nd the global optimum of a convex quadratic
objective function where the constraints are a conjunction of linear arithmetic equalities
9and inequalities. Quadratic programming has been widely studied in operations
research and interior point methods provide polynomial time algorithms for
solving such problems.
In Section 2 we saw how to encode the layout adjustment problem as a constrained
optimization problem in which the objective function  is a convex quadratic for-
mula. Unfortunately, the constraints cannot be expressed as conjunctions of linear
arithmetic constraints since the no overlap constraints involve disjunction.
To use a quadratic programming based approach, we need to replace these disjunctive
constraints by linear approximations which will guarantee that the no
overlap constraints hold. Since each individual disjunct is a linear constraint, the
straightforward way to do this is to choose which disjunctive possibility must hold.
In order to construct the linear approximation of the no-overlap constraints C no
with respect to the x direction (C no
x ) we dene the \right horizontal neighbours" of
nodes. We then constrain each node to have no overlap with its right neighbours.
In a sense we hardwire into the constraints which direction the nodes must move
in to remove the overlapping.
For any node v, its right horizontal neighbour nodes set right(v) is the set containing
all nodes u such that in the initial position: (1) u 6= v; (2) u is to the right
of v
v ); and (3) u and v could overlap if moved only in the x direction
(either x 0
or x 0
right(v) is an immediate right horizontal neighbour node of node v if
there does not exist a node u such right(v).
Similarly we can dene the upper vertical neighbour nodes set, upper(v), and
immediate upper vertical neighbour node, u v .
It is straightforward to dene the constraints in C no
x That is for each node v 2 V ,
we compute its immediate right horizontal neighbours, and for each of these, r v
say, add the constraint
into C no
x . Similarly we dene C no
y .
Generation of the orthogonal ordering constraints C oo
x and C oo
y for the x and y
directions, respectively, is conceptually straightforward. For e-ciency it is important
to eliminate as many redundant constraints as possible. The precise algorithm
is given in [10]
We treat the layout adjustment problem as two separate optimization problems,
one for the x dimension and one for the y dimension, by breaking the optimization
function into two parts and the constraint into two parts. The constraints in the
direction C x are given by C no
x together with the C oo constraints on x variables
x ). We similarly dene C y .
For the dynamic layout adjustment problem it follows from the denition of  dyn
that the optimization problems are to
subject to C x (6)
quadratic-opt
compute C x
x := minimize  x subject to C x
compute C y
y := minimize  y subject to C y

Figure

3. Quadratic programming approach to layout adjustment
for the x-direction, and
subject to C y (7)
for the y-direction. The new layout is given by x and y where x is the solution to
and y is the solution to (7).
The advantage in separating the problem in this way is twofold. First, it improves
e-ciency since it roughly halves the number of constraints considered in
each problem. Second, if we solve for the x-direction rst, it allows us to delay
the computation of C y to take into account the node overlapping which has been
removed by the optimization in the x-direction.
The actual layout adjustment algorithm used is given in Figure 3. First the
problem in the x dimension is solved. Then x 0 is reset to be x, the x positions
discovered by this optimization. Doing this may reduce the number of upper vertical
neighbours and so reduce the size of C y and also allow more
exibility in node
placement in the y-direction.
As we previously observed, polynomial time algorithms for solving quadratic programming
problems exist. However, for medium sized problems of several hundred
to one thousand constraints the preferred method of solution is an active set
method. We have used an incremental implementation of the active set method
provided by the C++ QOCA constraint solver [5]. The key idea behind the active
set method is to solve a sequence of constrained optimization problems O 0 , ., O t .
Each problem minimizes f with respect to a set of equality constraints, A, called
the active set. The active set consists of the original equality constraints plus those
inequality constraints that are \tight," in other words, those inequalities that are
currently required to be satised as equalities. The other inequalities are ignored
for the moment.
5. Using the EGENET Solver
In this section, we investigate how the EGENET solver can be used to solve the
layout adjustment problem. In order to use quadratic programming we needed
to linearize the no-overlap constraints and implicitly xed choices about whether
to remove the overlap in the vertical or the horizontal direction. This means that
potentially better solutions to the layout adjustment problem were never considered.
EGENET can handle the disjunctive no-overlap constraints directly and hence is
attractive as a method for solving the constrained optimization problems associated
with layout adjustment. But, because this formulation is non-convex only a local
optimum can be found.
In the remainder of this section we rst review the original EGENET model for
solving discrete constrained satisfaction problems. We then examine how to modify
the original EGENET to handle continuous constrained satisfaction problems
(without optimization). Lastly, we discuss how the modied EGENET can be used
to solve the layout adjustment problem as a continuous constrained optimization
problem. To our knowledge, this work represents the rst attempt to investigate
how the EGENET solver can be used to solve continuous constrained optimization
problems.
5.1. The Original EGENET Solver
A constraint satisfaction problem (CSP) [16] is a tuple (U; D;C), where U is a nite
set of variables, D denes a nite set D z , called the domain of z, for each z 2 U ,
and C is a nite set of constraints restricting the combination of values that the
variables can take. A solution is an assignment of values from the domains to their
respective variables so that all constraints are satised simultaneously. CSPs are
well-known to be NP-hard in general.
GENET [27] is an articial neural network, based on the min-con
ict heuristic
(MCH), for solving arbitrary CSPs with binary constraints. The MCH is to assign
a value causing the minimum number of constraint con
icts to each variable so
as to quickly nd the local minima in the search space. Lee et. al. [12] extended
GENET to EGENET with a generic representation scheme for handling both binary
and non-binary constraints. EGENET has been successfully applied to solve non-binary
CSPs such as the car-sequencing problems and cryptarithmetic problems in
an e-cient manner [12].
Constraints in EGENET are represented by functions from values of the variables
to non-negative numbers. For example the constraint z 1  z 2 can be represented
by the function
Alternatively we can represent the same constraint just using a Boolean valued
function, as
A general CSP can be formulated as a a discrete unconstrained optimization
problem as follows.
min z2D
zn is the Cartesian product of the (nite) domains for
all the n variables, m is the total number of constraints, and g i (z) denotes the
penalty function for each constraint C i in the CSP, and  i represents the weight
given to the constraint. The penalty g i (z) equals 0 if the variable assignment z
returns a positive integer. The weights associated with
constraints are all initially 1, but may be modied by the EGENET procedure. In
this formulation, the goal is to minimize the output of the cost function f(z) whose
value depends on the number of unsatised constraints and the weights associated
with these constraints. For each solution z  to the original CSP, f(z
satises all the constraints.
EGENET uses a simple local search rule to minimize the cost function f(z), and
a heuristic learning rule to change weights of constraints until it nds a solution
z  . Initially, a complete and random variable assignment z 0 is generated. Then,
the network executes a convergence procedure as follows. Each variable is asynchronously
updated in each convergence cycle. The update simply nds the value
for each variable which gives lowest total cost without modifying any other vari-
ables. When there is no change in any value assigned to the variables, the network
is trapped in a local minima. If the local minimum does not represents a solution,
a heuristic learning rule, is used to update the weight  i for any violated constraint
C i in the CSP so as to help the network escape from these local minima. The net-work
convergence procedure iterates until a solution is found or a predetermined
resource limit is exceeded.
5.2. The Modied EGENET Solver
The original EGENET solver only supports constraints over nite domains. There-
fore, to solve the layout adjustment problems with the EGENET approach, we have
to consider how to modify the original EGENET solver so as to handle problems
with continuous domains.
To handle such a continuous constrained problem, we have to decide how to
represent the real-number domain of each variable in an EGENET network. The
domain of each variable in a CSP is nite and is usually represented by a nite set
of contiguous integers. For continuous constrained problems, this is inappropriate,
since, even if we consider that real variables only take
oating point values, there
are too many possibilities. Instead we represent the range of possible values of a
variable z i simply by a lower and upper bound l i ::u i .
For problems with no natural lower and upper bounds on variables we need to
generate them. The tighter the bounds used the more e-cient the search will be
since it examines a smaller area. But giving initial bounds which are too tight may
lead to no solution being found even when one does exist.
Since the original EGENET variable updating function assumes a nite number
of possible values in the domain of each variable, to update a continuous variable
in the modied EGENET network, we need to treat the domain of each continuous
variable represented as a range l as a set with nite number of elements
bounded by the values l and u only. In other words, we sample the domain of a
continuous variable by only trying a nite number of possible values in its range,
when updating its value within the EGENET computation. The number of elements
we try in each update is called the domain sampling size. The larger the
domain sampling size the closer to the true local optimum solution we are likely to
get, but the more computation is required at each step. We use a domain sampling
size of 10 throughout our experiments, although this could be changed (even within
a computation).
In order to overcome the coarseness of the search when using a small domain
sampling size without increasing the computational overhead too greatly, whenever
a solution is found we can revise the bounds of variables inwards towards the
solution just found. This has the eect of focusing the search around the solution
just found. This approach is used in the algorithm below. This extra
exibility
makes our algorithm substantially dierent from the case where the domain sizes
of the variables remain xed throughout the computation (as used for discrete
constrained optimization and satisfaction problems).
To handle a continuous constrained optimization problem we simply add a optimization
component to the function to be minimized. The augmented cost function
is
As we shall see in the next section, this is closely related to the Lagrange multiplier
methods.
Pseudo-code for the general optimization algorithm EGENET-opt is given in Figure
4. The algorithm takes the domain sampling size DSZ, the number n of
variables in z and the cost function cost() as input, and returns a tuple consisting
of the best solution found z b and its cost best. The basic idea is similar to that of
GLS [25]. First, we initialize all the EGENET variables using initialize vars (usually
this is just random). Then, we use the var order function to produce a permutation
perm which determines the order in which the variables z will be updated. The core
of the method is the updating loop where each of the sample values for a variable
z v are tried in turn, and the value which gives minimum cost is retained as the
new value. This represents a simple local search on the best value of variable z v .
Because the cost function includes penalties for violated constraints this will drive
the search towards solutions.
This loop continues until a local minima is found (where no variable is updated).
When the local minimum represents a solution, EGENET-opt invokes the function
revise bounds to try to revise the bounds for the domains of the EGENET variables.
Then, it computes the solution cost according to the cost function, and updates the
best solution x b and best if the cost of the current solution is smaller than best. To
modify the augmented cost function, EGENET-opt invokes penalize ctr(z), which
is basically the same as the original EGENET heuristic learning mechanism, to
penalize any violated constraint with respect to the current variable assignment.
Similarly, EGENET-opt invokes penalize opt(z) to modify the form of the optimization
function that occurs in the augmented cost function. The algorithm iterates
until the function stopping criterion detects that a predened stopping criterion is
fullled, and therefore returns true.
initialize vars(z)
z b := z
best := cost(z b )
repeat
repeat
perm := var order(n)
mincost := cost(z)
minval := z v ;
if cost(z) < mincost
mincost := cost(z)
minval := z v ;
endif
endfor
z v := minval
endfor
until (no update for all v 2 z)
if (z represents a solution)
revise bounds(z)
if (cost(z) < best)
z b := z
best := cost(z b )
endif
endif
penalize ctr(z)
penalize opt(z)
until (stopping criterion())
return hz b ; besti

Figure

4. A General EGENET-based Optimization Algorithm
Clearly, the e-ciency of using EGENET-opt to solve a continuous constrained
optimization problem, and the quality 2 of the best solution found by EGENET-
opt depends largely on how we dene the augmented cost function, and how we
appropriately modify this cost function by the penalize ctr and penalize opt function.
5.3. Handling Layout Adjustment
The variables of the layout adjustment problem are x and y, the x and y coordinates
of each node. Given the
exible representation scheme for any general constraint
in the EGENET model, it is straightforward to dene a no-overlap constraint as a
disjunctive constraint in the EGENET network, which ensures that there will be
no overlapping between the labels i and j, as follows:

Figure

5 shows how the constraint is represented in the modied EGENET net-
work. It denes a function g ij which measures the amount of overlap in the x and
y directions, returning 0 if there is no overlap. A no-overlap constraint is applied
to each pair (i; j) of nodes where 1  i < j  n. This demonstrates one advantage
of using the EGENET approach to solve the layout adjustment problems : it is, in
general, simple to represent the constraints involved in these problems or other related
graph layout problems in the EGENET network. Indeed arbitrary additional
constraints can be added to the problem straightforwardly.
fx fy
fy

Figure

5. The EGENET network for a no-overlap constraint.
We need to determine suitable ranges for the variables of the problem, in order
to make use of the modied EGENET algorithm above. We would like to ensure
that the variables' initial ranges contains a solution to the problem, if it exists. A
conservative approach is to nd a solution using the uniform scaling approach and
then to use the minimal range containing that position and the original value. For
instance, if (x u
v ) is the position computed by the uniform scaling approach for
node v and the position of node v in the original graph is is
then the initial
range for x v can be set to [x otherwise, and similarly for
y v . Clearly this range is guaranteed to include at least one solution. The problem
is that scaling factors tend to be large, so the range is also large.
In practice, by making some assumptions about the density of the nodes we
can start with smaller ranges, and thus reduce the search. Dene max x to be the
maximum overlap in the x direction of any pair of nodes, and dene max y similarly.
We use initial ranges of [x 0
for y v . This means no solution is guaranteed, but this is only true for graph where
there is a dense overlapping in the initial layout. In practice this is rare.
For layout adjustment problems the initial value for the variables x and y returned
by initialize vars is given by the initial layout x 0 and y 0 . One of the reasons for
investigating local search methods is that this initial layout is usually quite close
to the global optimum, and hence local search around the initial layout is likely to
nd a good solution.
The variable ordering strategy var order used simply updates the variables in one
dimension (x) in a random order before or after updating the variables in the other
dimension (y). This is eective since the relationship between the x and y variables
are weak (only through disjunctive constraints). By evaluating each dimension in
turn we get a faster convergence to local minima. Other strategies are, of course,
possible.
The revise bounds function is dened as follows. When a solution is found at x
then for each x i , if x i > x 0
i , we reset the upper bound to be the current value x i and
the lower bound is reset to x 0
i we reset the lower bound to be the current
value x i and the upper bound is reset to x 0
the bounds are unchanged.
Similarly for y. This encodes the strategy that, since we have found a solution on
one side of the starting point, we will not look on the other side, and we will not
look further away as looking farther away will tend to reduce the optimality of the
solution.
For the graph layout problem, stopping criterion returns true when a predetermined
number of iterations have been tried, or when the cost of the current solution
is worse than or equal to the previous solution. The total resource limit is initially
set to 1000. Each time a better solution is found, the resource limit is reset to
double the amount of resource used to nd the previous solution if this is less than
100. Otherwise, the resource limit is reset to the minimum of 1000 or 120% of the
resource used when nding the previous solution.
All that remains is to determine the penalize ctr and penalize opt functions. The
relative weights of the objective function and the constraint penalties are impor-
tant. For example, for the graph layout adjustment problem, if the augmented cost
function is biased towards the penalty for constraint violation, that is node over-
lapping, then EGENET-opt may take a longer time, or even fail, to return a good
solution. 3 On the other hand, if the augmented cost function is biased towards
the solution cost, then EGENET-opt may fail to nd a solution satisfying all the
no-overlap constraints.
Recall the objective function  dyn for layout adjustment. As the quantity
(usually in the order of 100 or 1000) is always much larger than
the penalty value of the constraints (which are Boolean) for constraint violations,
we need to normalize this quantity so as to avoid bias towards the solution cost.
If the range of x v is [l v ::u v ] then the maximum value of the term
of (l v c x . Denote this by omax v . The normalized optimization
function for x v is simply
norm x
Clearly, the value returned by norm x real number in the range of
We can similarly dene a normalized optimization function norm y for variables y.
Accordingly, we dene the augmented cost function cost(x; y) as as the sum of the
penalty for constraint violations, and the sum of normalized optimization function
as follows.
(norm x
where m denotes the total number of constraints in the problem.
When a local minimum is found, the penalty function penalize opt changes the
normalized optimization functions to take into account the new smaller ranges for
some variables. The penalize ctr function simply increases the weight  i of a violated
constraint by 1 (as in the original EGENET model).
Note that in the EGENET approach we have ignored the orthogonal ordering
constraints, and simply concentrated on the overlap constraints. Since, in practice,
we have found that minimimizing  dyn preserves the structure of the original graph,
and so tends to preserve orthogonality, even though there are not explicit constraints
to do so.
6. Using A Pseudo-Lagrangian Method
The EGENET local search method described in the previous section is a modica-
tion of a discrete constrained satisfaction algorithm to solve continuous constrained
optimization problems. In the end, it looks very similar to a Lagrange multiplier
method. This inspired us to directly solve the problem using such an approach.
6.1. Lagrangian Multiplier Methods
Lagrange multiplier methods are a general approach to continuous constrained optimization
that can tackle non-linear objective functions with non-linear constraints.
A general continuous equality-constrained objective function is formulated as follows

minimize f(z) subject to
where f(z) is the objective function and g(z) is a vector of functions representing
the constraint penalties.
The Lagrangian function associated with this problem is a weighted sum of the
objective function and the constraints. It is dened as :
where  is a vector of Lagrange multipliers. The Lagrangian function is related to
the local extrema of the problem (8) by the following theorem (see e.g. [13]).
Theorem 1 Let z be a local extremum of f(z) subject to g(z). Assume that z is a
regular point 4 . Then there exists a vector  such that
r z f(z)

Figure

6. Overlap calculation.
Based on the above theorem there are a number of method for solving constrained
optimization problems. The most widely used is the rst-order method represented
as an iterative process:
z
where  k is a step-size parameter. Intuitively the equations represent counteracting
forces to achieve a good solution to the optimization problem. When a constraint
is violated (11) increases the weight of the constraint, forcing the search towards a
solution. In contrast (10) performs descent in the optimization direction once all
of the Lagrange multipliers are xed.
6.2. Layout Adjustment with Lagrange Multipliers
The Lagrangian approach to layout adjustment performs an iterative process like
that dened above. Rather than a synchronous update of all variables at once,
each node v is treated in turn, and its two coordinate variables x v and y v are
updated together. This allows the non-overlap constraints to be handled in a more
meaningful way.
When two nodes i and j overlap as illustrated in Figure 6, then the overlap
of j on i in eect creates a force on i in the direction shown. If node i moves
either a distance dx ij in the x direction or dy ij in the y direction the overlap will
disappear. We choose the minimum magnitude of dx ij or dy ij as the resulting
constraint violation. In eect, we treat the constraint function g ij as follows:
(0; do not overlap
Given this denition then r x i
otherwise, and
similarly r y i
The two constraint functions g ij and g ji are symmetric and represent a single
underlying overlap constraint. Hence, for each pair we have a
Lagrange multiplier  ij representing the current weight of the constraint. The basic
local search is then simply a Lagrangian optimization using a rst-order stepping.
Since the optimization only nds a local minima, one optimization may not nd a
very good solution. After a local minima is reached the pseudo-Lagrangian method
reduces the step-size by half, and also moves the nodes closer to their positions in
the initial layout since this will further decrease the objective function albeit at the
risk of introducing overlapping. This lets the search potentially nd better solu-
tions. Eventually after some number of such reoptimizations the method nishes,
returning the best solution found. For the experiments the initial stepsize was 0.125
and the factor limit 255. The function initialize multiplier simply initialized all the
Lagrange multipliers to 1. The resource limit was never exceeded.
The algorithm in Figure 7 does not take into account the orthogonal ordering
constraints. These could be added using the standard Lagrangian approach of
adding new constraint functions, namely
and
Unfortunately this simple addition can lead to divergent behaviour.
One simple approach to handle the equality constraints of the orthogonal ordering
is instead to simply force their compliance. Let S be a set of coordinates which
must all be equal, e.g. fx g. For each such set we compute the average
x2S x)=jSj and set each value within to this average value, e.g. x 1 :=
This approach while seemingly ad-hoc, has quite a principled
justication. If we replaced the set of variables S by a single variable (in eect
using the equation constraints as substitutions) then the change in this variable
would be determined from the sum of the changes of the variables in the set S.
The average is simply a function of the sum of the changes of the variables in S.
However, this approach does not handle the inequality constraints of the orthogonal
ordering.
As for the EGENET approach, in our empirical evaluation of the Langrangian
approach we have not included constraints to preserve the original orthogonal or-
dering, since again in practice, we have found that minimimizing  dyn preserves
the structure of the original graph, and so tends to preserve orthogonality.
initialize multiplier()
best := +1
stepsize := initial step size
repeat
if (i 6=
endif
endfor
endfor
if (g(x;
if (x; y) < best
best := (x; y)
else
stepsize := stepsize=2
initialize multiplier()
endif
endif
until (factor > limit or resource limit exceeded)
return

Figure

7. Pseudo-Lagrangian method for layout adjustment
7. Empirical Evaluation
In this section we compare the performance of the Scaling Algorithm (SCALE)
presented in Section 3, the Force Scan Algorithm (FSA) of Misue et al [17], the
quadratic solver approach (QUAD) presented in Section 4, the modied EGENET
solver described in Section 5 and the Psuedo-Lagrangian method (PLM) discussed
in Section 6 on a set of nine dynamic graph layout adjustment problems.
QUAD is implemented in Borland C++ for Windows Version 4:5. The other
solvers are implemented in C, and compiled by the GCC compiler Version 2:7:3 on
Linux. All tests were performed on a Pentium PC running at 155Mhz.
Table

1. CPU time taken by SCALE, FSA, QUAD, EGENET and PLM
for layout adjustment of the example problems.
Graph # nodes SCALE FSA QUAD EGENET PLM

Table

2. Value of  dyn in the adjusted layout using SCALE, FSA, QUAD,
EGENET and PLM for layout adjustment on the example problems.
Graph # nodes SCALE FSA QUAD EGENET PLM
9 17 38880 127008  77760 5535 3688
A quantitative comparison of these dierent methods on the sample problems is
provided in Table 1 and 2. In each table, the rst column gives the identifying
number for the graph while the second column gives the number of nodes in the
sample graph. Table 1 details the CPU time in seconds taken to nd the adjusted
layout for each method while Table 2 details the value of  dyn for the adjusted
layout given by each method.
For local search methods such as EGENET and PLM, the averages of CPU time
and cost over 10 successful runs are reported in each case. For all the cases we have
tested, both EGENET and PLM can successfully nd an (sub-)optimal nal layout
without node overlapping. It should be noted that for both EGENET and PLM,
the solvers will halt when the current solution found is worse than the previous
one. For EGENET, the solver will also halt after the, possibly reset, resource limit
is exceeded.
Broadly speaking we nd that the ranking of methods with respect to the CPU
time taken to nd the adjusted layout, from fastest to slowest, is SCALE, FSA,
QUAD, PLM and EGENET. SCALE and FSA are considerably faster than the
other methods, QUAD somewhat faster than PLM and the modied EGENET
solver takes much longer than the other solvers. This is probably because the
modied EGENET solver can only consider a nite number of points in the domains
of each variable for each updating, and slowly revise the domains after each learning.
The values of  dyn reported in Table 2 provide a simple numerical measure of the
quality of the adjusted layout. However, it is also important to look at the actual
aesthetic quality of the adjusted layout. For this reason we now look at each of the
example graphs and show the resulting layout adjustment with each method. Note
that we have used an asterisk (  ) to indicate the method giving the (subjectively)
best layout for each example in Table 2.
(a) Graph 1, general (b) Graph 1 with box nodes
(c) Layout with SCALE (d) Layout with FSA
Layout with QUAD (f) Layout with EGENET (g) Layout with PLM

Figure

8. Initial and layout adjustment for Graph 1.

Figure

8(a) and 8(b) respectively show the initial layout of Graph 1 as an idealized
graph with circles as nodes and as a labelled graph. Figure 8(c), 8(d), 8(e), 8(f)
and 8(g) give the resulting layout adjustment using SCALE, FSA, QUAD, mod-
ied EGENET and PLM respectively. All methods provide reasonable layout ad-
justment, although we note that EGENET introduces an edge/node label overlap.
PLM gives the best adjustment.
Note that, as in all of our gures, we have scaled each graph to have a maximum
height or width of one inch. Thus the adjusted layouts may not have the same
scale. Smaller (usually better) layouts may be identied by their relatively larger
node labels.
(a) Graph 2 Layout with SCALE (c) Layout with FSA
(d) Layout with QUAD (e) Layout with EGENET (f) Layout with PLM

Figure

9. Initial and resulting layouts for Graph 2.
Surprisingly for Graph 2 as shown in Figure 9, the simplest method SCALE nds
the best layout, while the other methods only nd a local minimum. All methods
give reasonable layout adjustment with QUAD giving the worst layout.

Figure

shows the initial and resulting layouts for Graph 3 which has been
chosen as an example of the kind of explanation diagram widely used in Biology
or Engineering textbooks. Arguably, QUAD gives the best adjusted layout since
it best preserves the original graph's structure. SCALE increases the size by too
much while EGENET and to a lesser extent PLM change the orthogonal ordering
of the graph and remove its symmetry.
Graph 4 as shown in Figure 11(a) is an example of a rooted tree. Such labelled
graphs are commonly used to display data structures or organization structures in
many real-life applications. All methods give reasonable layout. The worst is by
SCALE since it unnecessarily increases the size, while the layout found by QUAD
is slightly better than that found by PLM and EGENET.
Graph 5 is another example of rooted tree layout. This time PLM gives the best
layout, although it has changed the orthogonal ordering, closely followed by FSA
which preserves the orthogonal ordering. Both QUAD and EGENET introduce an
edge/label crossing.
Graph 6 was carefully designed to show that layout adjustment may introduce
edge crossings even though the layout adjustment method preserves the graph's
orthogonal ordering. Both FSA and QUAD produce the worst layouts since they
introduce edge crossing. SCALE does not introduce any edge crossing in the nal
a) Graph 3 (b) Layout with SCALE (c) Layout with FSA
(d) Layout with QUAD (e) Layout with EGENET (f) Layout with PLM

Figure

10. Initial and resulting layouts for Graph 3.
(a) Graph 4 (b) Layout with SCALE (c) Layout with FSA
(d) Layout with QUAD (e) Layout with EGENET (f) Layout with PLM

Figure

11. Graph 4 | tree layout adjustment (1).
layout since the initial layout does not contain any edge crossing, but the resulting
layout is, as usual, unnecessarily wide. The modied EGENET and PLM methods
produce very similar (and good) layouts with that produced by EGENET slightly
better than that produced by PLM.
As shown in Figure 14(a), Graph 7 is a rather pathological graph with no edges
but with lots of node overlapping occurred at dierent horizontal levels. SCALE
clearly gives the worst layout adjustment while the modied EGENET gives the
best layout which is neatly packed and fairly close to the initial layout. On the other
hand, PLM gives a stack-like layout which looks quite dierent from the original
graph.
a) Graph 5 (b) Layout with SCALE (c) Layout with FSA
(d) Layout with QUAD (e) Layout with EGENET (f) Layout with PLM

Figure

12. Graph 5 | tree layout adjustment (2).
Graph 8 shown in Figure 15(a) is a simplied version of Graph 7 with some nodes
removed. Thus, there is less node overlapping in Graph 8. All of the algorithms
produce a result closer to the original graph, but in this case PLM gives the most
aesthetically pleasing layout.
Graph 9 is an X-shaped graph with symmetry about both the x- and y-axis.
All layouts are reasonable. The layouts by SCALE, FSA and QUAD retain the
symmetry while those produced by the modied EGENET and PLM do not. QUAD
produces the best layout.
As we can see no method produces uniformly better layout adjustment, even
SCALE produces the best layout for one example. However in general, SCALE and
FSA produce the worst layout. In general, PLM closely followed by QUAD produce
the best layout. However, EGENET and PLM can lose the original structure of
the graph and to preserve this structure we would need to add extra constraints
into the modied EGENET and PLM solvers. Generally, QUAD and FSA preserve
the structure, in part because they preserve the orthogonal ordering, but may still
introduce edge overlapping not found in the original graph. SCALE is guaranteed
to preserve all of the original structure since it performs a simple uniform scaling.
(a) Graph 6 without node labels (b) Graph 6 with node labels
(c) Layout with SCALE (d) Layout with FSA (e) Layout with QUAD
(f) Layout with EGENET (g) Layout with PLM

Figure

13. Initial and resulting layouts for Graph 6.
7.1. Resource-bounded Layout Adjustment
Although the PLM solver produces the best layout, Table 1 suggests that it is
substantially slower than the SCALE and FSA solvers. A natural question to ask
is, given a (small) xed amount of time, which method will give the best layout?
This question makes sense because the PLM solver employs local search techniques
and at any point in time has a current best solution. Thus we can stop the PLM
solver after any time interval and look at the quality of the solution and compare
this to that of the SCALE and FSA solvers. It does not make sense to perform
the same experiment with QUAD since there is no concept of \the current best
solution."
The graph in Figure 17 shows the cost of the best solution found so far (as a
multiple of the best found eventually) versus time for the graphs 1, 7 and 9 during
the execution of the PLM algorithm. The rst non-overlapping solution is found
for each graph within 0.02 seconds. Except for Graph 9 the value of  dyn for this
solution is smaller than that of the solution eventually found by SCALE, FSA or
a) Graph 7 (b) Layout with SCALE (c) Layout with FSA
(d) Layout with QUAD (e) Layout with EGENET (f) Layout with PLM

Figure

14. Initial and resulting layouts for Graph 7.
(a) Graph 8 (b) Graph 8 by SCALE (c) Graph 8 by FSA
(d) Graph 8 by QUAD (e) Graph 8 by EGENET (f) Graph 8 by PLM

Figure

15. Initial and resulting layouts for Graph 8.
a) Graph 9 (b) Layout with SCALE (c) Layout with FSA
(d) Layout with QUAD (e) Layout with EGENET (f) Layout with PLM

Figure

16. Initial and resulting layouts for Graph 9.
QUAD (for Graph 9 the rst solution has cost 8108). For each of the graphs PLM
nds a solution whose value of  dyn is within 20% of the eventual best in less than
half the time required to nd the best. For these examples we could safely stop
PLM after 0.15 seconds and obtain a solution within 20% of the best found and, in
better than any solution found by the other algorithms.
8. Conclusion
We have studied the problem of layout adjustment for graphs in which we wish to
remove node overlapping while preserving the graph's original structure and hence
the user's mental map of the graph.
We have given four algorithms to solve this problem, all of which rely on viewing
it as a constrained optimization problem. Empirical evaluation of our algorithms
shown that they are reasonable fast and give nice layout, which is better than
that of the comparable algorithm, the FSA of Misue et al. Generally speaking,
the approach based on Lagrangian methods gives the best layout in a reasonable
time. However, it may not preserve the orthogonal layout of the original graph.
The quadratic programming approach also produces good layout in a reasonable
time and does preserve the graph's orthogonal ordering. Uniform scaling gives the
fastest and simplest approach to layout adjustment. It may lead to unnecessary
enlargement of the graph, but is guaranteed to preserve all of the original structure
in the graph.
Our results are not only interesting for layout adjustment of graphs: They also
suggest techniques for laying out non-overlapping windows and labels in maps.
graph 9
graph 7
graph 1

Figure

17. Cost of best solution found so far against time for graphs 1, 7, and 9
9.

Acknowledgement

We would like to thank Peter Eades for his comments on our work, and Yi Xiao
for the quadratic solver.
Notes
1. Note that unless the number of pixels is used, real numbers are usually used to denote the
positions and sizes of the nodes in a graph layout since it allows greater
exibility.
2. Even though the global optimality of the resulting solution cannot be guaranteed by the
EGENET approach as a local search method, the experimental results of the related GLS
approach reported in [25] show that for a set of the real-life military frequency assignment
problems GLS always found better solutions than those found by conventional search methods.
3. Here, we mean a solution with its cost close enough to the globally optimal cost of the optimization
problem.
4. A regular point of constraints g is one where rg 1 are linearly independent.



--R

Boltzmann machines for traveling salesman problems.
A discrete stochastic neural network algorithm for constraint satisfaction problems.
Algorithms for drawing graphs: an annotated bibliography.

Solving linear arithmetic constraints for user interface applications.
GENET: A connectionist architecture for solving constraint satisfaction problems by iterative improvement.
Solving small and large scale constraint satisfaction problems using a heuristic-based microgenetic algorithm
Online animated graph drawing using a modi
Preserving the mental map of a diagram.
Removing node overlapping using constrained optimization.
Extending GENET for Non-Binary CSP's
Towards a more e-cient stochastic constraint solver


busting in anchored graph drawing.
Consistency in networks of relations.
Layout adjustment and the mental map.
Experimental and theoretical results in interactive orthogonal graph drawing.
Edge: an extendible graph


Automatic graph drawing and readablity of diagrams.
Foundations of Constraint Satisfaction.
The tunneling algorithm for partial csps and combinatorial optimization problems.
Partial constraint satisfaction problems and guided local search.
Methods of Optimization.
Solving satisfaction problems using neural-networks
--TR

--CTR
Huang , Wei Lai, Force-transfer: a new approach to removing overlapping nodes in graph layout, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.349-358, February 01, 2003, Adelaide, Australia
Wanchun Li , Peter Eades , Nikola Nikolov, Using spring algorithms to remove node overlapping, proceedings of the 2005 Asia-Pacific symposium on Information visualisation, p.131-140, January 01, 2005, Sydney, Australia
Huang , Wei Lai , A. S. M. Sajeev , Junbin Gao, A new algorithm for removing node overlapping in graph visualization, Information Sciences: an International Journal, v.177 n.14, p.2821-2844, July, 2007
Huang , Peter Eades , Wei Lai, A framework of filtering, clustering and dynamic layout graphs for visualization, Proceedings of the Twenty-eighth Australasian conference on Computer Science, p.87-96, January 01, 2005, Newcastle, Australia
constrained optimization;graph layout;disjunctive constraints