Skip to main content
Top

2004 | Book

Graph Drawing

11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers

Editor: Giuseppe Liotta

Publisher: Springer Berlin Heidelberg

Book Series : Lecture Notes in Computer Science

insite
SEARCH

About this book

The 11th International Symposium on Graph Drawing (GD 2003) was held on September 21–24, 2003, at the Universit` a degli Studi di Perugia, Perugia, Italy. GD 2003 attracted 93 participants from academic and industrial institutions in 17 countries. In response to the call for papers, the program committee received 88 re- larsubmissionsdescribingoriginalresearchand/orsystemdemonstrations.Each submission was reviewed by at least 4 program committee members and c- ments were returned to the authors. Following extensive e-mail discussions, the program committee accepted 34 long papers (12 pages each in the proceedings) and 11 short papers (6 pages each in the proceedings). Also, 6 posters (2 pages each in the proceedings) were displayed in the conference poster gallery. In addition to the 88 submissions, the program committee also received a submission of special type, one that was not competing with the others for a time slot in the conference program and that collects selected open problems in graph drawing. The aim of this paper, which was refereed with particular care andUNCHANGEDtworoundsofrevisions,istostimulatefutureresearchinthe graph drawing community. The paper presents 42 challenging open problems in di?erentareasofgraphdrawingandcontainsmorethan120references.Although the length of the paper makes it closer to a journal version than to a conference extended abstract, we decided to include it in the conference proceedings so that it could easily reach in a short time the vast majority of the graph drawing community.

Table of Contents

Frontmatter

Planarity and Planar Drawings

Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way

We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to draw, in a crossing-free manner, graphs—such as software interaction diagrams—that would normally have many crossings. The main idea of this approach is quite simple: we allow groups of edges to be merged together and drawn as “tracks” (similar to train tracks). Producing such confluent diagrams automatically from a graph with many crossings is quite challenging, however, so we offer two heuristic algorithms to test if a non-planar graph can be drawn efficiently in a confluent way. In addition, we identify several large classes of graphs that can be completely categorized as being either confluently drawable or confluently non-drawable.

Matthew Dickerson, David Eppstein, Michael T. Goodrich, Jeremy Yu Meng
An Experimental Study of Crossing Minimization Heuristics

We present an extensive experimental study of heuristics for crossing minimization. The heuristics are based on the planarization approach, so far the most successful framework for crossing minimization. We study the effects of various methods for computing a maximal planar subgraph and for edge re-insertion including post-processing and randomization.

Carsten Gutwenger, Petra Mutzel
Stop Minding Your P’s and Q’s: Implementing a Fast and Simple DFS-Based Planarity Testing and Embedding Algorithm

In this paper we give a new description of the planarity testing and embedding algorithm presented by Boyer and Myrvold [2], providing, in our opinion, new insights on the combinatorial foundations of the algorithm. Especially, we give a detailed illustration of a fundamental phase of the algorithm, called walk-up, which was only succinctly illustrated in [2]. Also, we present an implementation of the algorithm and extensively test its efficiency against the most popular implementations of planarity testing algorithms. Further, as a side effect of the test activity, we propose a general overview of the state of the art (restricted to efficiency issues) of the planarity testing and embedding field.

John M. Boyer, Pier Francesco Cortese, Maurizio Patrignani, Giuseppe Di Battista
Bounds and Methods for k-Planar Crossing Numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K2 k + 1, q, for k ≥ 2. We prove tight bounds for complete graphs.

Farhad Shahrokhi, Ondrej Sýkora, Laszlo A. Székely, Imrich Vrt’o

Geometric Graph Theory

How Many Ways Can One Draw a Graph?

Using results from extremal graph theory, we determine the asymptotic number of string graphs with n vertices, i.e., graphs that can be obtained as the intersection graph of a system of continuous arcs in the plane. The number becomes much smaller, for any fixed d, if we restrict our attention to systems of arcs, any two of which cross at most d times. As an application, we estimate the number of different drawings of the complete graph K n with n vertices under various side conditions.

János Pach, Géza Tóth
Two Results on Intersection Graphs of Polygons

Intersection graphs of convex polygons inscribed to a circle, so called polygon-circle graphs, generalize several well studied classes of graphs, e.g., interval graphs, circle graphs, circular-arc graphs and chordal graphs. We consider the question how complicated need to be the polygons in a polygon-circle representation of a graph.Let cmp (n) denote the minimum k such that every polygon-circle graph on n vertices is the intersection graph of k-gons inscribed to the circle. We prove that cmp(n) = n − log2n + o(log2n) by showing that for every positive constant c < 1,cmp(n) ≤ n − clogn for every sufficiently large n, and by providing an explicit construction of polygon-circle graphs on n vertices which are not representable by polygons with less than n − logn − 2 loglogn corners. We also show that recognizing intersection graphs of k-gons inscribed in a circle is an NP-complete problem for every fixed k ≥ 3.

Jan Kratochvíl, Martin Pergel
Stretching of Jordan Arc Contact Systems

We prove that a contact system of Jordan arcs is stretchable if and only if it is extendable into a weak arrangement of pseudo-lines.

Hubert de Fraysseix, Patrice Ossona de Mendez
Noncrossing Hamiltonian Paths in Geometric Graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: Determine a function h, where h(n) is the largest number k such that when we remove arbitrary set of k edges from a complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that $h(n)=\Omega(\sqrt{n})$. We also determine the function exactly in case when the removed edges form a star or a matching, and give asymptotically tight bounds in case they form a clique.

Jakub Černý, Zdeněk Dvořák, Vít Jelínek, Jan Kára

Applications and Systems – Part I

GraphAEL: Graph Animations with Evolving Layouts

GraphAEL extracts three types of evolving graphs from the Graph Drawing literature and creates 2D and 3D animations of the evolutions. We study citation graphs, topic graphs, and collaboration graphs. We also create difference graphs which capture the nature of change between two given time periods. GraphAEL can be accessed online at http://graphael.cs.arizona.edu.

Cesim Erten, Philip J. Harding, Stephen G. Kobourov, Kevin Wampler, Gary Yee
Visualizing Related Metabolic Pathways in Two and a Half Dimensions

We propose a method for visualizing a set of related metabolic pathways using $2\frac{1}{2}$D graph drawing. Interdependent, two-dimensional layouts of each pathway are stacked on top of each other so that biologists get a full picture of subtle and significant differences among the pathways. Layouts are determined by a global layout of the union of all pathway-representing graphs using a variant of the proven Sugiyama approach for layered graph drawing that allows edges to cross if they appear in different graphs.

Ulrik Brandes, Tim Dwyer, Falk Schreiber
GoVisual for CASE Tools Borland Together ControlCenter and Gentleware Poseidon – System Demonstration

The Unified Modeling Language (UML) has become the software industry’s standard notation for representing software architecture and design models. UML diagrams play an important role in the engineering and re-engineering processes of software systems. Of particular interest from the Graph Drawer’s perspective are UML class diagrams whose purpose is to display class hierarchies (generalizations), associations, aggregations, and compositions in one picture. The combination of hierarchical and non-hierarchical relations poses a special challenge to a graph layout tool. We present an implementation of our technology within well-known modelling tools.

Carsten Gutwenger, Joachim Kupke, Karsten Klein, Sebastian Leipert

Straight-Line, Circular, and Circular-Arc Drawings

Area-Efficient Drawings of Outerplanar Graphs

We show that an outerplanar graph G with n vertices and degree d admits a planar straight-line grid drawing with area O(dn1.48) in O(n) time. This implies that if d =o(n0.52), then G can be drawn in this fashion in o(n2) area.

Ashim Garg, Adrian Rusu
A Framework for User-Grouped Circular Drawings

In this paper we introduce a framework for producing circular drawings in which the groupings are user-defined. These types of drawings can be used in applications for telecommunications, computer networks, social network analysis, project management, and more. This fast approach produces drawings in which the user-defined groupings are highly visible, each group is laid out with a low number of edge crossings, and the number of crossings between intra-group and inter-group edges is low.

Janet M. Six, Ioannis (Yanni) G. Tollis
Fixed-Location Circular-Arc Drawing of Planar Graphs

In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of n points on the plane, where n is the number of vertices in the graph. If for every edge we have only two possible circular arcs, then a simple reduction to 2SAT yields an O(n2) algorithm to find out if a drawing with no crossings can be realized. We present an improved O(n7/4polylogn) time algorithm. For the special case where the possible circular arcs for each edge are of the same length, we present an even more efficient algorithm that runs in O(n3/2polylogn) time. We also consider the problem if we have more than two possible circular arcs per edge and show that the problem becomes NP-Hard. Moreover, we show that two optimization versions of the problem are also NP-Hard.

Alon Efrat, Cesim Erten, Stephen G. Kobourov
A More Practical Algorithm for Drawing Binary Trees in Linear Area with Arbitrary Aspect Ratio

Trees are usually drawn using planar straight-line drawings. [1] presented an algorithm for constructing a planar straight-line grid drawing of an n-node binary tree with area O(n) and any pre-specified aspect ratio in the range [n − α,nα], where 0 ≤ α < 1 is any constant, in $\mathcal{O}(n {\rm log}n)$ time. Unfortunately, the algorithm of [1] is not suitable for practical use. The main problem is that the constant hidden in the “Oh” notation for area is quite large (e.g., it can be as large as 3900).In this paper, we have made several practical improvements to the algorithm, which make it suitable for practical use. We have also conducted experiments on this newer version of the algorithm for randomly-generated and complete binary trees with up to 50,000, and 65,535 nodes, respectively. Our experiments show that it constructs area-efficient drawings in practice, with area at most 10 times and 8 times the number of nodes for randomly-generated and complete binary trees, respectively.

Ashim Garg, Adrian Rusu

Symmetries

An Integer Programming Approach to Fuzzy Symmetry Detection

The problem of exact symmetry detection in general graphs has received much attention recently. In spite of its NP-hardness, two different algorithms have been presented that in general can solve this problem quickly in practice [5,2]. However, as most graphs do not admit any exact symmetry at all, the much harder problem of fuzzy symmetry detection arises: a minimal number of certain modifications of the graph should be allowed in order to make it symmetric. We present a general approach to this problem: we allow arbitrary edge deletions and edge creations; every single modification can be given an individual weight. We apply integer programming techniques to solve this problem exactly or heuristically and give runtime results for a first implementation.

Christoph Buchheim, Michael Jünger
Barycentric Drawings of Periodic Graphs

We study barycentric placement of vertices in periodic graphs of dimension 2 or higher. Barycentric placements exist for every connected periodic graph, are unique up to affine transformations, and provide a versatile tool not only in drawing, but also in computation. Example applications include symmetric convex drawing in dimension 2 as well as determining topological types of crystals and computing their ideal symmetry groups.

Olaf Delgado-Friedrichs

3D-Drawings

Three-Dimensional Grid Drawings with Sub-quadratic Volume

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A $\mathcal{O}(n^{3/2})$ volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was $\mathcal{O}(n^{2})$. These results (partially) solve open problems due to Pach, Thiele, and Tóth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001].

Vida Dujmović, David R. Wood
Laying Out Iterated Line Digraphs Using Queues

In this paper, we study a layout problem of a digraph using queues. The queuenumber of a digraph is the minimum number of queues required for a queue layout of the digraph. We present upper and lower bounds on the queuenumber of an iterated line digraph Lk(G) of a digraph G. In particular, our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the result on the queuenumber of Lk(G), it is shown that for any fixed digraph G, Lk(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in Lk(G). We also apply these results to particular families of iterated line digraphs such as de Bruijn digraphs, Kautz digraphs, butterfly digraphs, and wrapped butterfly digraphs.

Toru Hasunuma
Track Drawings of Graphs with Constant Queue Number

A k-track drawing is a crossing-free 3D straight-line drawing of a graph G on a set of k parallel lines called tracks. The minimum value of k for which G admits a k-track drawing is called the track number of G. In [9] it is proved that every graph from a proper minor closed family has constant track number if and only if it has constant queue number. In this paper we study the track number of well-known families of graphs with small queue number. For these families we show upper bounds and lower bounds on the track number that significantly improve previous results in the literature. Linear time algorithms that compute track drawings of these graphs are also presented and their volume complexity is discussed.

Emilio Di Giacomo, Henk Meijer
3D Visibility Representations of Complete Graphs

This paper continues the study of 3D visibility representations of complete graphs where vertices are represented by equal convex polygons lying in planes parallel to the xy-plane. Edges correspond to the z-parallel visibility among these polygons.We give several bounds on the size of the largest complete graph that has a 3D visibility representation with particular properties. Namely we improve the best known lower bound for representations by regular n-gons from $\lfloor \frac{n+1}{2}\rfloor+2$ to n+1 and the upper bound from $2^{2^{n}}$ to $\left({6n-3 \atop 3n-1}\right)-3$.

Jan Štola
Drawing Series-Parallel Graphs on Restricted Integer 3D Grids

A k-track drawing is a crossing-free 3D straight-line grid drawing of a graph G on a set of k parallel lines called tracks. The minimum value of k for which G admits a k-track drawing is called the track number of G. In the existing literature a lower bound of five and an upper bound of fifteen are known for the track number of series-parallel graph. In this paper we reduce this gap for a large subclass of series-parallel graph for which the lower bound remains five but we show an upper bound of eight. We also describe a linear time drawing algorithm that computes a 3D straight-line grid drawing of these graphs in volume 4 × 4 × 2n.

Emilio Di Giacomo
Nearly Optimal Three Dimensional Layout of Hypercube Networks

In this paper we consider the three-dimensional layout of hypercube networks. Namely, we study the problem of laying hypercube networks out on the three-dimensional grid with the properties that all nodes are represented as rectangular slices and lie on two opposite sides of the bounding box of the layout volume. We present both a lower bound and a layout method providing an upper bound on the layout volume of the hypercube network.

Tiziana Calamoneri, Annalisa Massini

Embeddings and Triangulations

Graph Embedding with Minimum Depth and Maximum External Face

We present new linear time algorithms using the SPQR-tree data structure for computing planar embeddings of planar graphs optimizing certain distance measures. Experience with orthogonal drawings generated by the topology-shape-metrics approach shows that planar embeddings following these distance measures lead to improved quality of the final drawing in terms of bends, edge length, and drawing area.Given a planar graph, the algorithms compute the planar embedding with1the minimum depth among the set of all planar embeddings of G,2the external face of maximum size among the set of all planar embeddings of G,3the external face of maximum size among the set of all embeddings of G with minimum depth.

Carsten Gutwenger, Petra Mutzel
More Efficient Generation of Plane Triangulations

In this paper we give an algorithm to generate all biconnected plane triangulations having exactly n vertices including exactly r vertices on the outer face. The algorithm uses O(n) space in total and generates such triangulations without duplications in O(rn) time per triangulation, while the previous best algorithm generates such triangulations in O(r2n) time per triangulation.

Shin-ichi Nakano, Takeaki Uno
Planar Embeddings of Graphs with Specified Edge Lengths

We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the planarity restrictions, which has close connections to rigidity theory, and where it is easy to see that the problem is NP-hard. In contrast, we show that the problem is tractable—indeed, solvable in linear time on a real RAM—for planar embeddings of planar 3-connected triangulations, even if the outer face is not a triangle. This result is essentially tight: the problem becomes NP-hard if we consider instead planar embeddings of planar 3-connected infinitesimally rigid graphs, a natural relaxation of triangulations in this context.

Sergio Cabello, Erik D. Demaine, Günter Rote

Applications and Systems – Part II

BGPlay: A System for Visualizing the Interdomain Routing Evolution

In this paper we describe the visual interface of BGPlay, an on-line service for the visualization of the behavior and of the instabilities of the Internet routing at the autonomous system level.A graph showing only connections among autonomous systems is not enough to convey all the information needed to fully understand the routing and its changes. BGPlay provides specifically tailored techniques and algorithms to show the routing at specific instants of time and to animate its changes. The system obtains routing data from well known on-line archives of routing information constantly kept up-to-date.

Giuseppe Di Battista, Federico Mariani, Maurizio Patrignani, Maurizio Pizzonia
GraphEx: An Improved Graph Translation Service

The Internet-based translation service GraphEX automatically converting between different graph formats, making it easier for users to take advantage of the full variety of graph drawing tools. GraphEx builds on the prototype translation component of the Graph Drawing Server [2], improving the handling of information mismatch problems and adding support for user-defined formats.

Stina Bridgeman
A Constrained, Force-Directed Layout Algorithm for Biological Pathways

We present a new elegant algorithm for layout of biological signaling pathways. It uses a force-directed layout scheme, taking into account directional and regional constraints enforced by different molecular interaction types and subcellular locations in a cell. The algorithm has been successfully implemented as part of a pathway integration and analysis toolkit named PATIKA and results with respect to computational complexity and quality of the layout have been found satisfactory.

Burkay Genc, Ugur Dogrusoz
Intersection-Free Morphing of Planar Graphs

Given two different drawings of a planar graph we consider the problem of morphing one drawing into the other. We designed and implemented an algorithm for intersection-free morphing of planar graphs. Our algorithm uses a combination of different techniques to achieve smooth transformations: rigid morphing, compatible triangulations, as well as morphing based on interpolation of the convex representations of the graphs. Our algorithm can morph between drawings with straight-line segments, bends, and curves. Our system is implemented in Java and available as an applet at http://gmorph.cs.arizona.edu.

Cesim Erten, Stephen G. Kobourov, Chandan Pitta

Fixed Parameter Tractability

Fixed Parameter Algorithms for one-sided crossing minimization Revisited

We exhibit a small problem kernel for the problem one-sided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we improve on the search tree algorithm developed in [5] and derive an O(1.4656k + kn2) algorithm for this problem, where k upperbounds the number of tolerated crossings of straight lines involved in the drawings of an n-vertex graph. Relations of this graph-drawing problem to the algebraic problem of finding a weighted linear extension of an ordering similar to [7] are exhibited.

Vida Dujmović, Henning Fernau, Michael Kaufmann
Experiments with the Fixed-Parameter Approach for Two-Layer Planarization

We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can efficiently minimum biplanarizing sets containing up to about 18 edges, thus making it comparable to previous integer linear programming approaches. We show how our implementation slightly improves the theoretical running time to O(6bpr(G) + |G |). Finally, we explain how our experimental work predicts how performance on sparse graphs may be improved.

Matthew Suderman, Sue Whitesides

Clusters, Cuts, and Orthogonal Drawings

Characterizing Families of Cuts That Can Be Represented by Axis-Parallel Rectangles

A drawing of a family of cuts of a graph is an augmented drawing of the graph such that every cut is represented by a simple closed curve and vice versa.We show that the families of cuts that admit a drawing in which every cut is represented by an axis-parallel rectangle are exactly those that have a cactus model that can be rooted such that edges of the graph that cross a cycle of the cactus point to the root. This includes the family of all minimum cuts of a graph. The proof also yields an efficient algorithm to construct a drawing with axis-parallel rectangles if it exists.

Ulrik Brandes, Sabine Cornelsen, Dorothea Wagner
Convex Drawing for c-Planar Biconnected Clustered Graphs

In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph is a graph with a set of non-intersecting clusters. In this paper, we assume that the graph is planar, each non leaf cluster has exactly two child clusters in the tree representation of non-intersecting clusters, and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight line segments with no crossing between two edges, and (ii) the boundary of the biconnected subgraph induced by each cluster is convex polygon.

Hiroshi Nagamochi, Katsutoshi Kuroya
Layout of Directed Hypergraphs with Orthogonal Hyperedges

We present a layout algorithm for directed hypergraphs. A hypergraph contains hyperedges that have multiple source and target nodes. Hyperedges are drawn with orthogonal segments. Nodes are organized in layers, so that for the majority of hyperedges the source nodes are placed in a higher layer than the target nodes, similar to traditional hierarchical layout [8,11]. The algorithm was implemented using ILOG JViews [10] for a project that targeted electrical signal visualization.

Georg Sander
No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs

A plane graph is a planar graph with a fixed embedding. In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this paper we consider a class of planar graphs, called subdividions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.

Md. Saidur Rahman, Noritsugu Egi, Takao Nishizeki

k-Level Drawings

Radial Level Planarity Testing and Embedding in Linear Time

Every planar graph has a concentric representation based on a breadth first search, see [21]. The vertices are placed on concentric circles and the edges are routed as curves without crossings. Here we take the opposite view. A graph with a given partitioning of its vertices onto k concentric circles is k-radial planar, if the edges can be routed monotonic between the circles without crossings. Radial planarity is a generalisation of level planarity, where the vertices are placed on k horizontal lines. We extend the technique for level planarity testing of [18,17,15,16,12,13] and show that radial planarity is decidable in linear time, and that a radial planar embedding can be computed in linear time.

Christian Bachmaier, Franz J. Brandenburg, Michael Forster
An Improved Approximation to the One-Sided Bilayer Drawing

Given a bipartite graph G=(V,W,E), a bilayer drawing consists of placing nodes in the first vertex set V on a straight line L1 and placing nodes in the second vertex set W on a parallel line L2. The one-sided crossing minimization problem asks to find an ordering of nodes in V to be placed on L1 so that the number of arc crossings is minimized. In this paper, we prove that there always exits a solution whose crossing number is at most 1.4664 times of a well-known lower bound that is obtained by summing up {c uv , c vu } over all node pairs u,vεV, where c uv denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering.

Hiroshi Nagamochi
Straight-Line Drawings of 2-Outerplanar Graphs on Two Curves

We study how to draw a 2-outerplane graph on two concentric circles, so that the internal (resp. external) vertices lie on the internal (resp. external) circle.

Emilio Di Giacomo, Walter Didimo

Force Directed and Energy-Based Techniques

An Energy Model for Visual Graph Clustering

We introduce an energy model whose minimum energy drawings reveal the clusters of the drawn graph. Here a cluster is a set of nodes with many internal edges and few edges to nodes outside the set. The drawings of the best-known force and energy models do not clearly show clusters for graphs whose diameter is small relative to the number of nodes. We formally characterize the minimum energy drawings of our energy model. This characterization shows in what sense the drawings separate clusters, and how the distance of separated clusters to the other nodes can be interpreted.

Andreas Noack
Simultaneous Graph Drawing: Layout Algorithms and Visualization Schemes

In this paper we consider the problem of drawing and displaying a series of related graphs, i.e., graphs that share all, or parts of the same vertex set. We designed and implemented three different algorithms for simultaneous graph drawing and three different visualization schemes. The algorithms are based on a modification of the force-directed algorithm that allows us to take into account vertex weights and edge weights in order to achieve mental map preservation while obtaining individually readable drawings. The implementation is in Java and the system can be downloaded at http://simg.cs.arizona.edu/.

Cesim Erten, Stephen G. Kobourov, Vu Le, Armand Navabi
Axis-by-Axis Stress Minimization

Graph drawing algorithms based on minimizing the so-called stress energy strive to place nodes in accordance with target distances. They were first introduced to the graph drawing field by Kamada and Kawai [11], and they had previously been used to visualize general kinds of data by multidimensional scaling. In this paper we suggest a novel algorithm for the minimization of the Stress energy. Unlike prior stress-minimization algorithms, our algorithm is suitable for a one-dimensional layout, where one axis of the drawing is already given and an additional axis needs to be computed. This 1-D drawing capability of the algorithm is a consequence of replacing the traditional node-by-node optimization with a more global axis-by-axis optimization. Moreover, our algorithm can be used for multidimensional graph drawing, where it has time and space complexity advantages compared with other stress minimization algorithms.

Yehuda Koren, David Harel
Drawing Graphs with Nonuniform Nodes Using Potential Fields

A potential field approach, coupled with force-directed methods, is proposed in this paper for drawing graphs with nonuniform nodes in 2-D and 3-D. In our framework, nonuniform nodes are uniformly or nonuniformly charged, while edges are modelled by springs. Using certain techniques developed in the field of potential-based path planning, we are able to find analytically tractable procedures for computing the repulsive force and torque of a node in the potential field induced by the remaining nodes. Our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of graphs in 2-D and 3-D can be produced efficiently.

Jen-Hui Chuang, Chun-Cheng Lin, Hsu-Chun Yen

Surfaces and Diagrams

Drawing Area-Proportional Venn and Euler Diagrams

We consider the problem of drawing Venn diagrams for which each region’s area is proportional to some weight (e.g., population or percentage) assigned to that region. These area-proportional Venn diagrams have an enhanced ability over traditional Venn diagrams to visually convey information about data sets with interacting characteristics. We develop algorithms for drawing area-proportional Venn diagrams for any population distribution over two characteristics using circles and over three characteristics using rectangles and near-rectangular polygons; modifications of these algorithms are then presented for drawing the more general Euler diagrams. We present results concerning which population distributions can be drawn using specific shapes. A program to aid further investigation of area-proportional Venn diagrams is also described.

Stirling Chow, Frank Ruskey
Optimal Pants Decompositions and Shortest Homotopic Cycles on an Orientable Surface

A pants decomposition of a compact orientable surface M is a set of disjoint simple cycles which cuts M into pairs of pants, i.e., spheres with three boundaries. Assuming M is a polyhedral surface, with weighted vertex-edge graph G, we consider combinatorial pants decompositions: the cycles are closed walks in G that may overlap but do not cross.We give an algorithm which, given a pants decomposition, computes a homotopic pants decomposition in which each cycle is a shortest cycle in its homotopy class. In particular, the resulting decomposition is optimal (as short as possible among all homotopic pants decompositions), and any optimal pants decomposition is made of shortest homotopic cycles. Our algorithm is polynomial in the complexity of the input and in the longest-to-shortest edge ratio of G. The same algorithm can be applied, given a simple cycle C, to compute a shortest cycle homotopic to C which is itself simple.

Éric Colin de Verdière, Francis Lazarus

Posters

Degree Navigator TM : The Journey of a Visualization Software

In this paper, we follow the evolution of a tool that has its roots in academic research on visualization and graph drawing. From its ancestor Order Explorer (1994) and initial version of 1995, to its latest version of 2003, we analyze the significant steps of a software that has gone from being a relatively simple, very specialized research tool to being a successful, widely deployed, complex commercial software used for academic degree audits. As the tool has expanded over the years, the initial scope has been completely outgrown and finding back the original idea in the current version is not completely obvious. Never the less, Degree NavigatorTM is a wonderful example of a research project that has gone a long way.

Guy-Vincent Jourdan, Ivan Rival, Nejib Zaguia
HexGraph: Applying Graph Drawing Algorithms to the Game of Hex

Hex [1] is a two player board game which is traditionally played on a rhombic hexagonal pattern (See Figure (1)). Players are assigned a colour and make moves by putting a token of their colour onto an empty field on the board. The first player to connect the two borders of the board in his colour by a path of his tokens on the board wins the game. Alternatively, Hex is played on an undirected, tricoloured (Red, Blue, Unclaimed) graph G [2]. The fields are represented by nodes and adjacent fields on the board are connected by an edge. The four borders of the board are represented by one node of equivalent colour each (See Figure(1)).

Colin Murray, Carsten Friedrich, Peter Eades
GLuskap: Visualization and Manipulation of Graph Drawings in 3-Dimensions

GLuskap

Breanne Dyck, Jill Joevenazzo, Elspeth Nickle, Jon Wilsdon, Stephen Wismath
Web-Linkage Viewer: Drawing Links in the Web Based on a Site-Oriented Framework

In recent years, link-based information retrieval methods from the Web are developed, such as HITS and Trawling. Since these methods utilize characteristic graph structures of links in the Web, analyzing the links by drawing them understandably will play an important role in the link-based information retrieval. Moreover, Asano et al.[2], [3] have shown that a framework using a site as a unit of information is more natural and useful for link-based information retrieval than the existing framework using a page as a unit. Therefore, we should distinguish links inside a site (called local-links) between links between sites (called global-links) and analyze their own graph structures. However, existing drawing tools, such as Gravis [1] and H3Viewer[5], do not distinguish local-links between global-links, and therefore they cannot draw graph structures of these links understandably. In this paper, we propose a new drawing tool, named Web-linkage Viewer, in order to draw graph structures in the Web according to the site-oriented framework.

Yasuhito Asano, Takao Nishizeki
The Puzzle Layout Problem

This poster describes an implementation of the puzzle generators and puzzle layouts introduced in [1].

Kozo Sugiyama, Seok-Hee Hong, Atsuhiko Maeda
Visual Data Mining with ILOG Discovery

Data mining deals with the discovery of useful and previously unknown knowledge from large data sets [3]. Traditional data mining tools use a combination of machine learning, statistical analysis, modeling techniques and database technology to find patterns, exceptions and subtle relationships in data. Typical applications include market segmentation, customer profiling, fraud detection, credit risk analysis, and business data development.

Thomas Baudel, Bruno Haible, Georg Sander

Graph Drawing Contest

Graph Drawing Contest Report

This report describes the Tenth Annual Graph Drawing Contest, held in conjunction with the 2003 Graph Drawing Symposium in Perugia, Italy. The purpose of the contest is to monitor and challenge the current state of the graph-drawing technology.

Franz J. Brandenburg, Ulrik Brandes, Peter Eades, Joe Marks

Invited Talks

Engineering and Visualizing Algorithms

We discuss some relevant issues in Algorithm Engineering, focussing on the interplay between theory and practice,and showing how it can integrate and reinforce the traditional theoretical approaches to the design and analysis of algorithms and data structures,while de- vising methodologies and tools for developing and engineering e .cient algorithmic codes.

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Report on the Invited Lecture by Pat Hanrahan, Titled “On Being in the Right Space”

The invited lecturer Pat Hanrahan is a professor at the Computer Science Department of Stanford University, Stanford CA 94305-9025, USA.The talk given by Prof. Hanrahan was about the connection between semantic constraints and aesthetics in graph drawing and information visualization. Examples were given of different application contexts where, in order to convey the right semantic information in a diagram, it is essential to respect geometric constraints concerning the shape of the edges and /or the relative position of the vertices. These examples include drawing maps (such as the map of the metro), visualizing (portions of) the Internet, and representing chemical maps.

Pat Hanrahan

Open Problems

Selected Open Problems in Graph Drawing

In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.

Franz Brandenburg, David Eppstein, Michael T. Goodrich, Stephen Kobourov, Giuseppe Liotta, Petra Mutzel
Backmatter
Metadata
Title
Graph Drawing
Editor
Giuseppe Liotta
Copyright Year
2004
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-24595-7
Print ISBN
978-3-540-20831-0
DOI
https://doi.org/10.1007/b94919