Report on the International Work Meeting on
Graph Drawing
Marino (Rome), Italy, June 4{5 1992

Giuseppe Di Battista

Roberto Tamassiay

dibattista@iasi.rm.cnr.it

rt@cs.brown.edu

Research on graph drawing has received increasing attention in the last years. This area
combines avors of topological graph theory, graph algorithms, and computational geometry,and has a wide range of applications including computer aided software engineering, project
management, network design, and visual interfaces.
A work meeting on graph drawing has taken place on June 4{5 at the Hotel Helio Cabalain Marino, near Rome. The goals of this meeting have been: (1) bringing together researchers
in graph drawing to assess the state of the art in the area by means of survey talks; and (2)developing further research activities, including workshops, schools, and conferences. While
the survey talks did not cover all aspects of graph drawing, they identi ed fundamental
combinatorial, algorithmic, and practical issues of the area. Due to the nature of the meeting,the number of participants was kept small.
The main nancial support was provided by the Progetto Finalizzato Sistemi Informatici
e Calcolo Parallelo of the Italian National Research Council. Additional support came fromthe Istituto di Analisi dei Sistemi ed Informatica of the Italian National Research Council,
by the Association pour the Developpement de l'Informatique dans le Sciences de l'Homme,
and by the Basic Research Action of the EC (ESPRIT II ALCOM).
The organizing committee consisted of Giuseppe Di Battista (Univ. Rome, Italy), Peter Eades (Univ. Newcastle, Australia), Pierre Rosenstiehl (EHESS, France), and Roberto
Tamassia (Brown Univ., USA). Local arrangements were handled by Paola Bertolazzi (IASICNR, Italy).
The complete program of the meeting and the abstracts of the talks are given below:
 Dipartimento di Informatica e Sistemistica, Universit
a di Roma \La Sapienza", Via Salaria 113, 00198
Rome, Italy.
y Department of Computer Science, Brown University, Providence, R.I. 02912{1910.

ProgramThursday, June 4

9:00{9:15 Welcome Address
9:15{10:15 Applications of Graph Drawing to Software Engineering, Carlo Batini (Univ. Rome, Italy)
10:15{11:15 Algorithms for Drawing Trees, Peter Eades (Univ. Newcastle,
Australia)
11:15{11:45 Co ee Break
11:45{12:45 Extremal Problems in Graph Drawing, Janos Pach (Hungarian
Academy of Sciences)
12:45{15:00 Lunch
15:00{16:00 Visibility Representations of Planar Graphs, Ioannis G. Tollis(Univ. of Texas at Dallas, USA)
16:00{16:30 Co ee Break
16:30{18:30 Partial Orders for Planarity and Drawings, Hubert de Fraysseix,
Patrice de Mendez, and Pierre Rosenstiehl (EHESS, France)
19:30 Dinner
21:30 Business Meeting

Friday, June 5

9:00{10:00 Drawing Compound Digraphs and its Application to an Idea Organizer, Kozo Sugiyama (Fujitsu, Japan)
10:00{11:00 Area Requirements, Giuseppe Di Battista (Univ. Rome, Italy)
11:00{11:30 Co ee Break
11:30{12:30 Angular Resolution of Straight-Line Drawings, Michael Kaufmann(Max Plank Inst., Germany)
12:30{15:00 Lunch
15:00{16:00 Algorithms for Orthogonal Drawings, Roberto Tamassia (Brown
Univ., USA)
16:00{16:30 Co ee Break
16:30{17:15 Circle Packing Representation in the Plane and Other Surfaces,
Bojan Mohar, (Univ. of Ljubjana, Slovenia)
17:15{17:45 Dynamic Graph Drawing, Robert F. Cohen (Brown Univ., USA)17:45{18:15 A New Method for Planar Graph Drawings on a Grid, Goos Kant
(Utrecht Univ., The Netherlands)
18:15{18:45 An Automatic Layout Facility, Giuseppe Liotta (Univ. Rome, Italy)
19:30 DinnerAbstracts

Applications of Graph Drawing to Software Engineering
Carlo Batini (Univ. Rome, Italy)

In several application areas of software engineering intermediate and nal products of thedesign activity are represented by means of diagrams. Diagrams present several advantages
over other representations, since they are an aid to clear thinking (a diagram is better thata thousand words). Diagrams are external representations of organization charts, data andfunction schemas, structure of procedure calls, pieces of code, etc. A diagram is characterized
by a meaning (the "piece of reality" it draws), and a syntax, expressed by: a graphic grammar,that de nes the types of symbols and connections allowed, aesthetic criteria adopted in
drawing the diagram. an underlying diagram model (e.g. hierarchical, planar, connected,etc). In software engineering tools, diagram are manipulated by several functions, such as
beauti cation, modi cation, re nement, merging of several diagrams, animation, etc. Eachone of such functions is characterized by speci c algorithms needed for the nal activityof diagram drawing. E.g. when we beautify a diagram we are interested to achieve someaesthetic criteria that were previously not respected; when we re ne a diagram into a moredetailed one, we are interested to maintain monotonicity of shape. Producing incrementallysuch a library by dynamically tailoring and merging paradigmatic algorithms, results in a
new and interesting research area.

Algorithms for Drawing TreesPeter Eades (Univ. Newcastle, Australia)
Several conventions for drawing rooted trees are discussed: classical drawings, tip-over drawings, inclusion drawings, and h-v drawings. In each convention, a number of algorithms andcomplexity results are available. For free trees (no speci c root), algorithms are mostly drawn
from folklore. Radial drawings, spring drawings, and orthogonal drawings are discussed.

Extremal Problems in Graph Drawing
Janos Pach (Hungarian Academy of Sciences)
A geometric graph (a convex geometric graph) is a pair (V; E ), where V is a set of points inthe plane in general position (in convex position), and E is a set of segments connecting somepoints in V . I survey many recent results in geometric graph theory with special emphasison the following questions. (A) What is the maximum number of edges a geometric graphwith n vertices can have without containing a given forbidden con guration (e.g., k pairwise
disjoint edges o k pairwise crossing edges, etc.)? (B) What is the largest number f (n) withthe property that any geometric graph of n vertices contains either f (n) pairwise disjointedges or f (n) pairwise crossing edges? (C) What is the maximum number of sides of a cell ina geometric graph with n vertices? Some generalizations to higher dimensions (for geometric
hypergraphs) are also considered.

Visibility Representations of Planar Graphs
Ioannis G. Tollis (Univ. of Texas at Dallas, USA)Interesting representations of graphs result from mapping vertices into horizontal segments

and edges into vertical segments drawn between visible vertex-segments. (Two parallel segments of a given set are visible if they can be joined by a segment orthogonal to them, which
does not intersect any other segment.) Such representations are called visibility representations. These representations nd applications in VLSI layout, algorithm animation, visuallanguages and CASE tools. We consider three types of visibility representations: (i) Weakvisibility representation, if two vertices are adjacent then their corresponding segments must
be visible. (ii) -visibility representation, where vertices can be represented by open, closed,or semiclosed horizontal segments in the plane such that two vertices are adjacent if andonly if their associated segments are visible. (iii) Strong-visibility representation, where vertices are represented by closed horizontal segments such that two vertices are adjacent if
and only if their corresponding segments are visible. We discuss various types of visibility
representations of planar graphs on the plane, cylinder, and sphere.

Partial Orders for Planarity and Drawings
Hubert de Fraysseix, and Pierre Rosenstiehl (EHESS, France)
A bipolar orientation of a graph appears often in the algorithm literature as a rst stepfor the generation of a particular drawing. Here the properties of bipolar orientations are
systematically explored in terms of circuits, cocircuits, rank activities, Tutte polynomial,
poset dimension, angle bipartition and max ow-min cut theorem. Ecient algorithms aredescribed to list, generate or extend bipolar orientations for general graphs or plane ones,
with or without constraints. (Joint work with Patrice de Mendez.)

Drawing Compound Digraphs and its Application to an Idea Organizer
Kozo Sugiyama (Fujitsu, Japan)
A compound digraph is a directed graph with both inclusion and adjacency edges and is
widely used in diverse elds. In this talk, rst, a heuristic method for automatically drawing
a compound digraph is presented. Then, several graphic interface techniques which facilitate
the method in organizing ideas such as direct manipulation, animation, incremental editing,sh-eyes (focusing, abridgements), and utilization of curves are discussed. Finally, it is emphasized that interface issues are important as well as algorithmic aspects of graph drawing.
(Joint work with K. Misue.)

Area Requirements
Giuseppe Di Battista (Univ. Rome, Italy)
An upward drawing of an acyclic digraph is a planar straight-line drawing with the additional
requirement that all the edges ow in the same direction, e.g., from bottom to top. The
literature on the problem of constructing upward drawings of important classes of digraphs
is surveyed. First, it is show that there is a family of binary trees with n vertices requiring(n log n) area for any upward drawing; moreover, that bound is tight, i.e. each binary treewith n vertices can be drawn with O(n log n) area. Second, motivated by the elegant H -treelayout algorithm for constructing non-upward drawings of complete binary trees, an algorithm
is presented for constructing an upward drawing of a complete binary tree with n vertices inO(n) area. This result is extended to the drawings of Fibonacci trees. Third, it is shown thatthe area requirement of upward drawings of series-parallel digraphs crucially depends on thechoice of planar embedding. Also, parallel and sequential drawing algorithms are presented
that are optimal with respect to both the time complexity and to the area achieved. Several
results show that while series-parallel digraphs have a rather simple and well understoodcombinatorial structure, naive drawing strategies lead to drawings with exponential area,
and clever algorithms are needed to achieve optimal area.

Angular Resolution of Straight-Line Drawings
Michael Kaufmann (Universitat Passau and Max-Planck-Institut Saarbrucken, Germany)
The angular resolution of a drawing of graph G is the minimum angle between two incident
edges that appears in the drawing. In this talk the state of the art is presented how to
maximize the angular resolution. First the general technique by Formann et al. [FOCS'90] isreviewed, then a re nement for planar graphs is given. A recent paper of Malitz/Papakostas[STOC'92] shows that planar graphs can be drawn planar with minimum angle only depending on the maximum degree of the vertices. At the end, some aspect on the relationship ofresolution and area are discussed.

Algorithms for Orthogonal Drawings
Roberto Tamassia (Brown Univ., USA)
An orthogonal drawing of a graph is such that the edges are represented by polygonal chainsconsisting of horizontal and vertical segments. The intermediate vertices of the chain (which
are not vertices of the graph) are called bends. In this talk we survey algorithms for constructing planar orthogonal drawings. The main quality measures considered are the minimizationof the number of bends and of the area of the drawing. The construction of planar orthogonaldrawings has many important applications, including graph visualization, VLSI layout, facilities oorplanning, and communication by light or microwave. Given an embedded planargraph G with n vertices, a planar orthogonal drawing of G with the minimum number ofbends can be computed in O(n2 log n) time using network- ow techniques. Drawings with
O(n) bends can be constructed in O(n) time using visibility representations. Also, there arefamilies of graphs that require (n) bends. Open problems include minimizing bends overall possible embeddings, and nding an ecient parallel algorithm for bend minimization.

Circle Packing Representation in the Plane and Other Surfaces
Bojan Mohar, (Univ. of Ljubjana, Slovenia)
The Andreev-Thurston circle packing theorem is generalized and improved in three ways.
First, to arbitrary maps on closed surfaces. Second, we get the simultaneous circle packingof the map and its dual map so that, in the corresponding straight-line representations of the
map and the dual, any two edges dual to each other cross at the right angle. The necessary
and sucient condition for a map to have such a primal-dual circle packing representationis that its universal cover is 3-connected (the map has no \planar" 2-separations). Finally, apolynomial time algorithm is obtained that given a map M and a rational number  > 0 nds
an -approximation for the primal-dual circle packing representation of M . In particular, we
get a polynomial time algorithm for geodesic convex representations of reduced maps onarbitrary surfaces.

Dynamic Graph Drawing
Robert F. Cohen (Brown Univ., USA)
Drawing graphs is an important problem that combines avors of computational geometry
and graph theory. Applications can be found in a variety of areas including circuit layout,
network management, software engineering, and graphics. The main contributions of thispaper can be summarized as follows: (i) We devise a model for dynamic graph algorithms,
based on performing queries and updates on an implicit representation of the drawing, andwe show its applications. (ii) We present several ecient dynamic drawing algorithms fortrees, series-parallel digraphs, planar st-digraphs, and planar graphs. These algorithms adopt
a variety of representations (e.g., straight-line, polyline, visibility), and update the drawing
in a smooth way. (iii) We show that the implicit representation of the layout used by ouralgorithms for trees and series-parallel digraphs also supports point-location and window
queries. (Joint work with P. Bertolazzi, G. Di Battista, R. Tamassia, and I.G. Tollis.)

A New Method for Planar Graph Drawings on a Grid
Goos Kant (Utrecht Univ., The Netherlands)
We introduce a new method to optimize the required area, minimum angle and number ofbends of planar drawings of graphs on a grid. The main tool is a new type of orderingon the vertices and faces of triconnected planar graphs. With this method linear time andspace algorithms can be designed for many graph drawing problems. (i) We show that every
triconnected planar graph G can be drawn convexly with straight lines on an (2n 4)  (n 2)grid. (ii) If G has maximum degree four (three), then G can be drawn orthogonal with at
most b 3n2 c + 3 (at most b n2 c + 1) bends on an n  n grid (d n2 e  d n2 e grid, respectively). (iii)
If G has maximum degree d, then G can be drawn planar on an (2n 6)  (3n 6) grid withminimum angle larger than d 1 2 radians and at most 5n 15 bends. These results give insome cases considerable improvements over previous results, and give new bounds in othercases. Several other results, e.g. concerning visibility representations, are included.

An Automatic Layout Facility
Giuseppe Liotta (Univ. Rome, Italy)
An automatic layout facility is a tool that receives as input a graph-like structure and isable to produce a diagram that nicely represents such a structure. Because of the increasing
number of systems that manage diagrams, automatic layout facilities and algorithms forgraphs layout have been extensively studied in the last years. We present a new approach indesigning an automatic layout facility. Our approach is based on a modular management of acollection of algorithms and on a tool that is able to automatically select the best algorithm
for a given application. Such approach has been used for devising the automatic layout facilityof Diagram Server, a network server that o ers to its clients several facilities for managing
diagrams. (Joint work with P. Bertolazzi and G. Di Battista.)