Computing Orthogonal Drawings with the Minimum Number of Bends.
AbstractWe describe a branch-and-bound algorithm for computing an orthogonal grid drawing with the minimum number of bends of a biconnected planar graph. Such an algorithm is based on an efficient enumeration schema of the embeddings of a planar graph and on several new methods for computing lower bounds of the number of bends. We experiment with such algorithm on a large test suite and compare the results with the state-of-the-art. The experiments show the feasibility of the approach and also its limitations. Further, the experiments show how minimizing the number of bends has positive effects on other quality measures of the effectiveness of the drawing. We also present a new method for dealing with vertices of degree larger than four.
Introduction
Various graphic standards have been proposed to draw graphs, each one devoted
to a specific class of applications. An extensive literature on the subject can be
found in [4, 23, 2]. In particular, an orthogonal drawing maps each edge into a
chain of horizontal and vertical segments and an orthogonal grid drawing is an
orthogonal drawing such that vertices and bends along the edges have integer
coordinates. Orthogonal grid drawings are widely used for graph visualization
in many applications including database systems (entity-relationship diagrams),
software engineering (data-flow diagrams), and circuit design (circuit schemat-
ics).
Research supported in part by the ESPRIT LTR Project no. 20244 - ALCOM-IT.
y IASI, CNR, viale Manzoni 30, 00185 Roma Italy.
z Dipartimento di Informatica e Automazione, Universit'a di Roma Tre, via della Vasca
Navale 84, 00146 Roma, Italy.
x Dipartimento di Informatica e Automazione, Universit'a di Roma Tre, via della Vasca
Navale 84, 00146 Roma, Italy.
Many algorithms for constructing orthogonal grid drawings have been proposed
in the literature and implemented into industrial tools. They can be
roughly classified according to two main approaches: the topology-shape-metrics
approach determines the final drawing through an intermediate step in which
a planar embedding of the graph is constructed (see, e.g., [21, 19, 22, 20]); the
draw-and-adjust approach reaches the final drawing by working directly on its
geometry (see, e.g., [1, 18]). Since a planar graph has an orthogonal grid drawing
iff its vertices have degree at most 4, both the approaches assume that vertices
have degree at most 4. Such a limitation is usually removed by "expanding"
higher degree vertices into two or more vertices. Examples of expansion techniques
can be found in [20].
In the topology-shape-metrics approach, the drawing is incrementally specified
in three phases. The first phase, planarization, determines a planar embedding
of the graph, by possibly adding ficticious vertices that represent crossings.
The second phase, orthogonalization, receives as input a planar embedding and
computes an orthogonal drawing. The third phase, compaction, produces the
final orthogonal grid drawing trying to minimize the area.
The orthogonalization step is crucial for the effectiveness of the drawing and
has been extensively investigated. A very elegant O(n 2 log n) time algorithm
for constructing an orthogonal drawing with the minimum number of bends of
an n-vertex embedded planar graph has been presented by Tamassia in [19]. It
is based on a minimum cost network flow problem that considers bends along
edges as units of flow.
However, the algorithm in [19] minimizes the number of bends only within the
given planar embedding. Observe that a planar graph can have an exponential
number of planar embeddings and it has been shown [6] that the choice of the
embedding can deeply affect the number of bends of the drawing. Namely,
there exist graphs that, for a certain embedding have a linear number of bends,
and for another embedding have only a constant number. Unfortunately, the
problem of minimizing the number of bends in a variable embedding setting
is NP-complete [10, 11]. Optimal polynomial-time algorithms for subclasses of
graphs are shown in [6].
Because of the tight interaction between the graph drawing area and applica-
tions, the attention to experimental work on graph drawing is rapidly increasing.
In [5] it is presented an experimental study comparing topology-shape-metrics
and draw-and-adjust algorithms for orthogonal grid drawings. The test graphs
were generated from a core set of 112 graphs used in "real-life" software engineering
and database applications with number of vertices ranging from 10 to 100.
The experiments provide a detailed quantitative evaluation of the performance
of seven algorithms, and show that they exhibit trade-offs between "aesthetic"
properties (e.g., crossings, bends, edge length) and running time. The algorithm
GIOTTO (topology-shape-metrics with the Tamassia's algorithm in the orthogonalization
step) performs better than the others at the expenses of a worst time
performance.
Other examples of experimental work in graph drawing follow. The performance
of four planar straight-line drawing algorithms is compared in [14].
Himsolt [12] presents a comparative study of twelve graph drawings algorithms;
the algorithms selected are based on various approaches (e.g., force-directed, lay-
ering, and planarization) and use a variety of graphic standards (e.g., orthogonal,
straight-line, polyline). The experiments are conducted with the graph drawing
system GraphEd [12]. The test suite consists of about 100 graphs. Brandenburg
and Rohrer [3] compare five "force-directed" methods for constructing straight-line
drawings of general undirected graphs. Juenger and Mutzel [15] investigate
crossing minization strategies for straight-line drawings of 2-layer graphs, and
compare the performance of popular heuristics for this problem.
In this paper, we present the following results. Let G be a biconnected planar
graph such that each vertex has degree at most 4 (4-planar graph).
ffl We describe a branch-and-bound algorithm called BB-ORTH that computes
an orthogonal grid drawing of G with the minimum number of bends in the
variable embedding setting. The algorithm is based on: several new methods
for computing lower bounds on the number of bends of a planar graph
(Section 3). Such methods give new insights on the relationships between
the structure of the triconnected components and the number of bends;
a new enumeration schema that allows to enumerate without repetitions
all the planar embeddings of G (Section 4). Such enumeration schema
exploits the capability of SPQR-trees [7, 8] in implicitely representing the
embeddings of a planar graph.
ffl We present a system that implements BB-ORTH. Such a system is provided
with a graphical interface that animates all the phases of the algorithm
and displays partial results, exploiting existing graph drawing algorithms
to represent all the graphs involved in the computation. The interaction
with the system allows to stop the computation once a sufficiently good
orthogonal drawing is displayed. (Section 5).
ffl We test BB-ORTH against a large test suite of randomly generated graphs
with up to 60 vertices and compare the experimental results with the best
state-of-the-art results (algoritm GIOTTO) (Section 6). Our experiments
show: an improvement in the number of bends of 20-30%; an improvement
of several other quality measures of the drawing that are affected from the
number of bends. For example the length of the longest edge of the drawings
obtained with BB-ORTH is about 50% smaller than the length of the
longest edge of the drawings obtained with GIOTTO; a sensible increasing of
the CPU-time that however is perfectly affordable within the typical size
of graphs of real-life applications [5].
ffl Also, BB-ORTH can be easily applied on all biconnected components of
graphs. This yields a powerful heuristic for reducing the number of bends
in connected graphs. Further, the limitation on the degree of the vertices
can be easily removed by using the expansion techniques cited above.
Preliminaries
We assume familiarity with planarity and connectivity of graphs [9, 17]. Since
we consider only planar graphs, we use the term embedding instead of planar
embedding.
An orthogonal drawing of a 4-planar graph G is optimal if it has the minimum
number of bends among all the possible orthogonal drawings of G. When
this is not ambiguous, given an embedding OE of G, we also call optimal the
porthogonal drawing of G with the minimum number of bends that preserves
the embedding OE.
Let G be a biconnected graph. A split pair of G is either a separation-pair
or a pair of adjacent vertices. A split component of a split pair fu; vg is either
an edge (u; v) or a maximal subgraph C of G such that C contains u and v,
and fu; vg is not a split pair of C. A vertex w distinct from u and v belongs to
exactly one split component of fu,vg.
are some pairwise edge disjoint split components of G
with split pairs respectively. The graph G 0 obtained by substituting
each of G
partial graph of G. We denote E virt (E nonvirt ) the set of (non-)virtual edges of
G 0 . We say that G i is the pertinent graph of e
is the representative edge of G i .
Let OE be an embedding of G and let OE 0 be an embedding of G 0 . We say that
OE preserves OE 0 if G 0
can be obtained from G OE by substituting each component
G i with its representative edge.
In the following we summarize SPQR-trees. For more details, see [7, 8].
SPQR-trees are closely related to the classical decomposition of biconnected
graphs into triconnected components [13].
Let fs; tg be a split pair of G. A maximal split pair fu; vg of G with respect
to fs; tg is a split pair of G distinct from fs; tg such that for any other split pair
of G, there exists a split component of fu containing vertices u, v,
s, and t.
be an edge of G, called reference edge. The SPQR-tree T of G
with respect to e describes a recursive decomposition of G induced by its split
pairs. Tree T is a rooted ordered tree whose nodes are of four types: S, P, Q,
and R. Each node  of T has an associated biconnected multigraph, called the
skeleton of , and denoted by skeleton(). Also, it is associated with an edge
of the skeleton of the parent  of , called the virtual edge of  in skeleton().
Tree T is recursively defined as follows.
If G consists of exactly two parallel edges between s and t, then T consists
of a single Q-node whose skeleton is G itself.
If the split pair fs; tg has at least three split components G
the root of T is a P-node . Graph skeleton() consists of k parallel edges
between s and t, denoted e
Otherwise, the split pair fs; tg has exactly two split components, one of them
is the reference edge e, and we denote with G 0 the other split component. If G 0
has cutvertices c that partition G into its blocks G
in this order from s to t, the root of T is an S-node . Graph skeleton() is the
cycle t, and e i connects c i\Gamma1 with c i
If none of the above cases applies, let fs be the maximal
split pairs of G with respect to fs; tg (k  1), and for be the
union of all the split components of fs but the one containing the reference
edge e. The root of T is an R-node . Graph skeleton() is obtained from G
by replacing each subgraph G i with the edge e i between s i and t i .
Except for the trivial case,  has children  k in this order, such that
i is the root of the SPQR-tree of graph G i [ e i with respect to reference edge
said to be the virtual edge of node  i in skeleton()
and of node  in skeleton( i ). Graph G i is called the pertinent graph of node
and of edge e i .
The tree T so obtained has a Q-node associated with each edge of G, except
the reference edge e. We complete the SPQR-tree by adding another Q-node,
representing the reference edge e, and making it the parent of  so that it
becomes the root.
Let  be a node of T . We have: if  is an R-node, then skeleton() is a triconnected
if  is an S-node, then skeleton() is a cycle; if  is a P-node,
then skeleton() is a triconnected multigraph consisting of a bundle of multiple
edges; and if  is a Q-node, then skeleton() is a biconnected multigraph
consisting of two multiple edges.
The skeletons of the nodes of T are homeomorphic to subgraphs of G. The
SPQR-trees of G with respect to different reference edges are isomorphic and are
obtained one from the other by selecting a different Q-node as the root. Hence,
we can define the unrooted SPQR-tree of G without ambiguity.
The SPQR-tree T of a graph G with n vertices and m edges has m Q-nodes
and O(n) S-, P-, and R-nodes. Also, the total number of vertices of the skeletons
stored at the nodes of T is O(n).
A graph G is planar if and only if the skeletons of all the nodes of the SPQR-
tree T of G are planar. An SPQR-tree T rooted at a given Q-node represents all
the planar embeddings of G having the reference edge (associated to the Q-node
at the root) on the external face.
3 Lower Bounds for Orthogonal Drawings
In this section we propose some new lower bounds on the number of bends of a
biconnected planar graph. The proofs of the theorems are omitted due to space
limitation.
E) be a biconnected 4-planar graph and H be an orthogonal
drawing of G, we denote by b(H) the total number of bends of H and by b E 0
the number of bends along the edges of E 0
subgraphs of G such that
be an optimal orthogonal drawing
of G i and let H be an orthogonal drawing of G. Then, b(H)
be an embedded partial graph of G and let H 0
be an orthogonal
drawing of G 0
. Suppose H 0
is such that b E nonvirt (H 0
an embedding OE of G that preserves OE 0 and an optimal orthogonal drawing H OE
of G OE .
From Property 1 and Lemma 1 it follows a first lower bound.
Theorem 1 Let E) be a biconnected 4-planar graph and G 0
an embedded
partial graph of G. For each virtual edge e i of G 0 ,
a lower bound on the number of bends of the pertinent graph G i of e i . Consider
an orthogonal drawing H 0
of G 0
such that b E nonvirt (H 0
be an embedding of G that preserves OE 0 , consider any orthogonal drawing H OE of
G OE . We have that:
Remark 1 An orthogonal drawing H 0
of G 0
such that b E nonvirt(HOE 0
can be easily obtained by using the Tamassia's algorithm [19]. Namely,
when two faces f and g share a virtual edge, the corresponding edge of the dual
graph in the minimum cost flow problem of [19] is set to zero.
A second lower bound is described in the following theorem.
Theorem 2 Let G OE be an embedded biconnected 4-planar graph and G 0
an
embedded partial graph of G, such that OE preserves OE 0 . Derive from G 0
the
embedded graph G OE 0 by substituting each virtual edge e i of G 0 ,
any simple path from u i to v i in G i . Consider an optimal orthogonal drawing
and an orthogonal drawing H OE of G OE . Then we have that:
The next corollary allows us to combine the above lower bounds into a hybrid
technique.
Corollary 1 Let G OE be an embedded biconnected 4-planar graph and G 0
an
embedded partial graph of G. Consider a subset F virt of the set of the virtual
edges of G 0
and derive from G 0
the graph G 00
by substituting each edge e i 2
F virt with any path from u i to v i in G i . Denote by E p the set of edges of G
introduced by such substitution. For each e be a lower
bound on the number of bends of the pertinent graph G j of e j . Consider an
orthogonal drawing H 00
of G 00
, such that b E nonvirt(HOE 0
Let H OE be an orthogonal drawing of G OE , we have that:
4 A Branch and Bound Strategy
Let G be a biconnected 4-planar graph. In this section we describe a technique
for enumerating all the possible orthogonal drawings of G and rules to avoid
examining all of them in the computation of the optimum.
The enumeration exploits the SPQR-tree T of G. Namely, we enumerate all
the orthogonal drawings of G with edge e on the external face by rooting T at e
and exploiting the capacity of T rooted at e in representing all the embeddings
having e on the external face. A complete enumeration is done by rooting T at
all the possible edges.
We encode all the possible embeddings of G, implicitely represented by T
rooted at e, as follows.
We visit the SPQR-tree such that a node is visited after its parent, e.g. depth
first or breadth first. This induces a numbering r of the P- and R-nodes
of T . We define a r-uple of variables r that are in one-to-one
correspondence with the P- and R-nodes  of T . Each variable x i of X
corresponding to a R-node  i can be set to three values corresponding to two
swaps of the pertinent graph of  i plus one unknown value. Each variable x j of
X corresponding to a P-node  j can be set to up to seven values corresponding
to the possible permutations of the pertinent graphs of the children of  j plus
one unknown value. Unknown values represent portions of the embedding that
are not yet specified.
A search tree B is defined as follows. Each node fi of B corresponds to a
different setting X fi of X . Such setting is partitioned into two contiguous (one
of them possibly empty) subsets x Elements of the
first subset contain values specifying embeddings while elements in the second
subset contain unknown values. Leaves of B are in correspondence with settings
of X without unknown values. Internal nodes of B are in correspondence with
settings of X with at least one unknown value. The setting of the root of B
consists of unknown values only. The children of fi (with subsets x
and x child for each
possible value of x h+1 .
Observe that there is a mapping between embedded partial graphs of G and
nodes of B. Namely, the embedded partial graph G fi of G associated to node fi
of B with subsets x obtained as follows. First, set
G fi to skeleton( 1 ) embedded according to x 1 . Second, substitute each virtual
edge e i of  1 with the skeleton of the child  i of  1 , embedded according to x i ,
only for 2  i  h. Then, recursively substitute virtual edges with embedded
skeletons until all the skeletons in fskeleton( 1 are used.
We visit B breadth-first starting from the root. At each node fi of B with
setting X fi we compute a lower bound and an upper bound of the number of
bends of any orthogonal drawing of G such that its embedding is (partially)
specified by X fi . The current optimal solution is updated accordingly. Children
are not visited if the lower bound is greater than the current optimum.
For each fi, lower bounds and upper bounds are computed as follows by using
the results presented in Section 3.
1. We construct G fi using an array of pointers to the nodes of T . Observe
that at each substitution of a virtual edge with a skeleton a reverse of the
adjacency lists might be needed.
2. We compute lower bounds. G fi is a partial graph of G, with embedding
derived from X fi . Let E virt be the set of virtual edges of G fi . For each
consider the pertinent graph G i and compute a lower bound b i
on the number of bends of G i using Theorem 1. For each e i such that the
value of such lower bound is zero we substitute in G fi edge e i with any
simple path from u i to v i in G i , so deriving a new graph G 0
fi . Denote by
F virt the set of such edges and by E p the set of edges of G introduced by
the substitution (observe that E p may be empty). By Remark 1 we apply
Tamassia's algorithm on G 0
, assigning zero costs to the edges of the dual
graph associated to the virtual edges. We obtain an orthogonal drawing
of G 0
with minimum number of bends on the set
) be such a number of bends. Then, by Corollary 1 we compute the
lower bound L fi at node fi, as
Lower bounds (b i ) can be pre-computed with a suitable pre-processing by
visiting T bottom-up. The pre-computation consists of two phases. We
apply Tamassia's algorithm on the skeleton of each R- and P-node, with
zero cost for virtual edges; in this way we associate a lower bound to each
R- and P-node of T . Note that these pre-computed bounds do not depend
on the choice of the reference edge, so they are computed only once, at
the beginning of BB-ORTH. We visit T bottom-up summing for each Rand
P-node  the lower bounds of the children of  to the lower bound
of . Note that these pre-computed bounds depend on the choice of the
reference edge, so they are re-computed at any choice of the reference edge.
3. We compute upper bounds. Namely, we consider the embedded partial
graph G fi and complete it to a pertinent embedded graph G OE . The embedding
of G OE is obtained by substituting the unknown values of X fi with
embedding values in a random way. Then we apply Tamassia's algorithm
to G OE so obtaining the upper bound. We also avoid multiple generations
of the same embedded graph in completing the partial graph.
We compute the optimal solution over all possible choices of the reference
edge. To do so, our implementation of SPQR-trees supports efficient evert oper-
ations. Also, to expedite the process we: reuse upper bounds computed during
computations referring to different choices of the virtual edge; avoid to compute
solutions referring to embeddings that have been already explored. If an edge e
that has already been reference edge appears on the external face of some G fi ,
since we have already explored all the embeddings with e on the external face,
we cut from the search tree all the descendants of fi.
One of the consequences of the above discussion is summarized in the following
theorem:
Theorem 3 Let G be a biconnected planar graph. The enumeration schema
adopted by BB-ORTH examines each planar embedding of G exactly once.
5 Implementation
The system has been developed with the C++ language and has full Leda [16]
compatibility. Namely, several classes of Leda have been refined into new classes:
Embedded Graphs, preserve the embedding for each update operation. We have
taken care of a new efficient implementation of several basic methods like DFS,
BFS, st-numbering, topological sorting, etc; Directed Embedded Graphs, with
several network flow facilities. In particular we implemented the minimum cost
flow algorithm that searches for minimum cost augmenting paths with the Dijkstra
algorithm, used in the original paper of Tamassia [19]. We implemented the
corresponding priority queues with the Fibonacci-heaps of Leda; Planar Embedded
Graphs, with faces and dual graph; Orthogonal planar embedded graphs, to
describe orthogonal drawings; Drawn Graphs, with several graphical attributes;
SPQR-trees, with several supporting classes, like split-components, skeletons,
etc. As far as we know, this is the first implementation of the SPQR-trees. Fur-
ther, to support experiments, we have developed a new Leda graph editor, based
on the previous Leda editor. The graphical interface shows an animation of the
algorithm in which the SPQR-tree is rooted at different reference edges. Also,
it displays the relationships between the SPQR-tree and the search tree and the
evolution of the search tree. Clicking at SPQR-tree nodes shows skeletons of
nodes. Of course, to show the animation, the graphical interface exploits several
graph drawing algorithms.
Fig. 1 shows a 17-verticed graph drawn by the GIOTTO, and by BB-ORTH,
respectively. Fig. 2 shows a 100-vertices graph drawn by the GIOTTO, and by
BB-ORTH, respectively.
Finally, we observe that a careful cases analysis of each P-node  allows
faster computations of preprocessing lower bounds; such analysis is based on the
number of virtual edges of the skeleton of , on the values of the precomputed
lower bounds of the children of  and on length of the shortest paths in the
pertinent graphs of the children of .
6 Experimental Setting and Computational Result

We have tested our algorithm against two randomly generated test suites
overall consisting of about 200 graphs. Such graphs are available on the web
(www.inf.uniroma3.it/people/gdb/wp12/LOG.html) and have been generated
as follows. It is well known that any embedded planar biconnected graph can
be generated from the triangle graph by means of a sequence of insert-vertex
and insert-edge operations. Insert-vertex subdivides an existing edge into two
new edges separated by a new vertex. Insert-edge inserts a new edge between
two existing vertices that are on the same face. Thus, we have implemented
a generation mechanism that at each step randomly chooses which operation
to apply and where to apply it. The two test suites differ in the probability
distributions we have given for insert-vertex and insert-edge. Also, to stress the
performance of the algorithm we have discarded graphs with "a small number"
of triconnected components. Observe that we decided to define a new test suite
instead of using the one of [5] because the biconnected components of those
graphs do not have a sufficiently large number of triconnected components (and
thus a sufficient number of different embeddings) to stress enough BB-ORTH.
For each drawing obtained by the algorithm, we have measured the following
quality parameters. bends: total number of edge bends. maxedgebends: max
number of bends on an edge. unifbends: standard deviation of the number of
edge bends. area: area of the smallest rectangle with horizontal and vertical sides
covering the drawing. totaledgelen: total edge length. maxedgelen: maximum
length of an edge. uniflen: standard deviation of the edge length. screenratio:
deviation of the aspect ratio of the drawing (width/height or height/width) from
the optimal one (4/3). Measured performance parameters are: cpu time, total
number of search tree nodes, number of visited search tree nodes.
Due to space limitations, we show the experimental results with respect to
only. They are summarized in the graphics of Fig. 3
On the x-axis we either have the number of vertices or the total number (RP)
of R- and P-nodes. All values in the graphics represent average values.
Fig. 3.A, 3.C and 3.D compare respectively the number of bends, the area and
the maxedgelen of the drawing of BB-ORTH with the ones of GIOTTO. Graphics
with white points represent the behavior of BB-ORTH. Graphics with black points
represent the behavior of GIOTTO. The improvement on the number of bends
positively affects all the quality measures. In Fig. 3.B, 3.D and 3.F we show the
percentages of the improvements.
Concerning performance, Fig. 3.G shows the CPU-time of BB-ORTH on a
RISC6000 IBM. The algorithm can take about one hour on graphs with
vertices. Finally, Fig. 3.H compares the number of nodes of the search tree and
the number of nodes that are actually visited. It shows that for high values of
RP the percentage of visited nodes is dramatically low (below 10 %).
7 Conclusions and Open Problems
Most graph drawing problems involve the solution of optimization problems that
are computationally hard. Thus, for several years the resarch in graph drawing
has focused on the development of efficient heuristics. However, the graphs to be
drawn are frequenly of small size (it is unusual to draw an Entity-Relationship
or Data Flow diagrams with more than 70-80 vertices) and the available work-stations
allow faster and faster computation. Also, the requirements of the users
in terms of aesthetic features of the interfaces is always growing.
Hence, recently there has been an increasing attention towards the development
of graph drawing tools that privilege the effectiveness of the drawing
against the efficiency of the computation (see e.g., [15]).
In this paper we presented an algorithm for computing an orthogonal drawing
with the minimum number of bends of a graph. The computational results that
we obtained are encouraging both in terms of the quality of the drawings and in
terms of the time performance.
Several problems are still open. For example: is it possible to apply variations
of the techniques presented in this paper to solve the upward drawability testing
problem? A directed graph is upward planar if it is planar and can be drawn
with all the edges following the same direction. The problem to test a directed
graph for upward drawability is NP-complete [10]; how difficult is it to find
an enumeration schema and lower bounds for the problem of computing the
orthogonal drawing in 3-space with the minimum number of bends?

Acknowledgements

We are grateful to Antonio Leonforte for implementing part of the system. We
are also grateful to Sandra Follaro, Armando Parise, and Maurizio Patrignani
for their support.



--R

A better heuristic for orthogonal graph drawings.
Graph Drawing
An experimental comparison of force-directed and randomized graph drawing algorithms
Algorithms for drawing graphs: an annotated bibliography.
An experimental comparison of three graph drawing algorithms.
Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs


Graph Algorithms.
On the computational complexity of upward and rectilinear planarity testing.
On the computational complexity of upward and rectilinear planarity testing.
Comparing and evaluating layout algorithms within GraphEd.
Dividing a graph into triconnected compo- nents
A note on planar graph drawing algorithms.
Exact and heuristic algorithms for 2-layer straightline crossing minimization
LEDA: a platform for combinatorial and geometric computing.
Planar graphs: Theory and algorithms.
Improved algorithms and bounds for orthogonal drawings.
On embedding a graph in the grid with the minimum number of bends.
Automatic graph drawing and readability of diagrams.
A unified approach to visibility representations of planar graphs.
Efficient embedding of planar graphs in linear time.
Graph Drawing
--TR

--CTR
Markus Eiglsperger , Michael Kaufmann , Martin Siebenhaller, A topology-shape-metrics approach for the automatic layout of UML class diagrams, Proceedings of the ACM symposium on Software visualization, June 11-13, 2003, San Diego, California
Giuseppe Di Battista , Walter Didimo , Maurizio Patrignani , Maurizio Pizzonia, Drawing database schemas, SoftwarePractice & Experience, v.32 n.11, p.1065-1098, September 2002
Markus Eiglsperger , Carsten Gutwenger , Michael Kaufmann , Joachim Kupke , Michael Jnger , Sebastian Leipert , Karsten Klein , Petra Mutzel , Martin Siebenhaller, Automatic layout of UML class diagrams in orthogonal style, Information Visualization, v.3 n.3, p.189-208, September 2004
planar embedding;orthogonal drawings;bends;branch and bound;planar graphs;graph drawing