Graph Drawing

We give a brief account of results concerning the number of triangulations on finite point sets in the plane, both for arbitrary sets and for specific sets such as the

n

×

n

integer lattice.

In recent years the development of graphics hardware and efficient rendering algorithms enabled game developers to create large landscapes and render them at interactive rates. However, the shown scenes are still rough approximations that do not reach the complexity of real nature. To obtain sufficient simulations with a degree of realism that comes close to nature, a couple of problems have to be solved. In this extended abstract these challenges are roughly sketched, references are given for further readings.

The typical use of force-directed layout is to create organic-looking, straight-edge drawings of large graphs while combinatorial techniques are generally preferred for high-quality layout of small to medium sized graphs. In this paper we integrate edge-routing techniques into a force-directed layout method based on constrained stress majorisation. Our basic procedure takes an initial layout for the graph, including poly-line paths for the edges, and improves this layout by moving the nodes to reduce stress and moving edge bend points to straighten the edges and reduce their overall length. Separation constraints between nodes and edge bend points are used to ensure that nodes do not overlap edges or other nodes and that no additional edge crossings are introduced.

Most force-directed graph drawing algorithms depend for speed crucially on efficient methods for approximating repulsive forces between a large number of particles. A combination of various tree data structures and multi-pole approximations has been successfully used by a number of authors. If a multi-level approach is taken, in the late (and due to the large number of particles computationally intensive) steps, movements of particles are quite limited. We utilize this fact by basing force-calculations on an easy updatable tree data structure. Using explicit distance checks instead of relying on implicit guarantees provided by quadtrees and avoiding local expansions of the multi-pole expansion leads to a very simple implementation that is faster than comparable earlier methods. The latter claim is supported by experimental results.

We present a fast spectral graph drawing algorithm for drawing undirected connected graphs. Classical Multi-Dimensional Scaling yields a quadratic-time spectral algorithm, which approximates the real distances of the nodes in the final drawing with their graph theoretical distances. We build from this idea to develop the linear-time spectral graph drawing algorithm SSDE. We reduce the space and time complexity of the spectral decomposition by approximating the distance matrix with the product of three smaller matrices, which are formed by sampling rows and columns of the distance matrix. The main advantages of our algorithm are that it is very fast and it gives aesthetically pleasing results, when compared to other spectral graph drawing algorithms. The runtime for typical 10

5

node graphs is about one second and for 10

6

node graphs about ten seconds.

We present a novel sampling-based approximation technique for classical multidimensional scaling that yields an extremely fast layout algorithm suitable even for very large graphs. It produces layouts that compare favorably with other methods for drawing large graphs, and it is among the fastest methods available. In addition, our approach allows for progressive computation, i.e. a rough approximation of the layout can be produced even faster, and then be refined until satisfaction.

We consider planar drawings of trees that must satisfy constraints on the angles between edges incident to a common vertex and on the distances between adjacent vertices. These requirements arise naturally in many applications such as drawing phylogenetic trees or route maps. For straight-line drawings, either class of constraints is always realizable, whereas their combination is not in general. We show that straight-line realizability can be tested in linear time, and give an algorithm that produces drawing satisfying both groups of constraints together in a model where edges are represented as polylines with at most two bends per edge or as continuously differentiable curves.

Given a tree

T

spanning a set of points

${\mathcal S}$

in the plane, we study the problem of drawing

T

using only line segments aligned with a fixed set of directions

${\mathcal C}$

. The vertices in the drawing must lie within a given distance

r

of each original point

$p \in {\mathcal S}$

, and an objective function counting the number of bends must be minimised. We propose five versions of this problem using different objective functions, and algorithms to solve them. This work has potential applications in geographic map schematisation and metro map layout.

We consider drawings of trees in which all edges incident to leaves can be extended to infinite rays without crossing, partitioning the plane into infinite convex polygons. Among all such drawings we seek the one maximizing the angular resolution of the drawing. We find linear time algorithms for solving this problem, both for plane trees and for trees without a fixed embedding. In any such drawing, the edge lengths may be set independently of the angles, without crossing; we describe multiple strategies for setting these lengths.

We show an algorithm for constructing 3

D

straight-line drawings of balanced constant degree trees. The drawings have linear volume and optimal aspect ratio. As a side effect, we also give an algorithm for constructing 2

D

drawings of balanced constant degree trees in linear area, with optimal aspect ratio and with better angular resolution with respect to the one of [8]. Further, we present an algorithm for constructing 3

D

poly-line drawings of trees whose degree is bounded by

n

1/3

in linear volume and with optimal aspect ratio.

We consider the problem of simultaneous embedding of planar graphs. We demonstrate how to simultaneously embed a path and an

n

-level planar graph and how to use radial embeddings for curvilinear simultaneous embeddings of a path and an outerplanar graph. We also show how to use star-shaped levels to find 2-bends per path edge simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms run in

O

(

n

) time.

We show that a planar graph and a tree can always be simultaneously embedded with fixed edges and that two outerplanar graphs generally cannot.

We show that every graph

G

with maximum degree three has a straight-line drawing in the plane using edges of at most five different slopes. Moreover, if

G

is connected and has at least one vertex of degree less than three, then four directions suffice.

Many practical applications demand additional restrictions on an admissible planar embedding. In particular, constraints on the permitted (clockwise) order of the edges around a vertex, like so-called

side constraints

, abound. In this paper, we introduce a set of hierarchical embedding constraints that also comprises side constraints. We present linear time algorithms for testing if a graph is

ec-planar

, i.e., admits a planar embedding satisfying the given embedding constraints, as well as for computing such an embedding. Moreover, we characterize the set of all possible ec-planar embeddings and consider the problem of finding a planar combinatorial embedding of a planar graph such that an additional edge can be inserted with the minimum number of crossings; we show that this problem can still be solved in linear time under the additional restrictions of embedding constraints.

A straight-line drawing of a plane graph is called an open rectangle-of-influence drawing if there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of every edge. In an inner triangulated plane graph, every inner face is a triangle although the outer face is not always a triangle. In this paper, we first obtain a sufficient condition for an inner triangulated plane graph

G

to have an open rectangle-of-influence drawing; the condition is expressed in terms of a labeling of angles of a subgraph of

G

. We then present an

O

(

n

1.5

/log

n

)-time algorithm to examine whether

G

satisfies the condition and, if so, construct an open rectangle-of-influence drawing of

G

on an (

n

 − 1) ×(

n

 − 1) integer grid, where

n

is the number of vertices in

G

.

Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrary planar graph to index the decomposition. We prove that every graph that excludes a fixed graph as a minor has a planar decomposition with bounded width and a linear number of bags.

The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. We prove that planar decompositions are intimately related to the crossing number, in the sense that a graph with bounded degree has linear crossing number if and only if it has a planar decomposition with bounded width and linear order. It follows from the above result about planar decompositions that every graph with bounded degree and an excluded minor has linear crossing number.

Analogous results are proved for the convex and rectilinear crossing numbers. In particular, every graph with bounded degree and bounded tree-width has linear convex crossing number, and every

K

3,3

-minor-free graph with bounded degree has linear rectilinear crossing number.

Crossing minimization is one of the most challenging algorithmic problems in topological graph theory, with strong ties to graph drawing applications. Despite a long history of intensive research, no practical “good” algorithm for crossing minimization is known (that is hardly surprising, since the problem itself is NP-complete). Even more surprising is how little we know about a seemingly simple particular problem: to minimize the number of crossings in an

almost planar

graph, that is, a graph with an edge whose removal leaves a planar graph. This problem is in turn a building block in an “edge insertion” heuristic for crossing minimization. In this paper we prove a constant factor approximation algorithm for the crossing number of almost planar graphs with bounded degree. On the other hand, we demonstrate nontriviality of the crossing minimization problem on almost planar graphs by exhibiting several examples, among them new families of crossing critical graphs which are almost planar and projective.

2000 Math Subject Classification:

05C10, 05C62, 68R10.

The crossing number cr(

G

) of a graph

G

is the minimum number of crossings over all drawings of

G

in the plane. In 1993, Richter and Thomassen [RT93] conjectured that there is a constant

c

such that every graph

G

with crossing number

k

has an edge

e

such that

${\rm cr}(G-e) \geq k-c\sqrt{k}$

. They showed only that

G

always has an edge

e

with

${\rm cr}(G-e) \geq \frac{2}{5}{\rm cr}(G)-O(1)$

. We prove that for every fixed

ε

 > 0, there is a constant

n

0

depending on

ε

such that if

G

is a graph with

n

 > 

n

0

vertices and

m

 > 

n

1 + 

ε

edges, then

G

has a subgraph

G

′ with at most

$(1-\frac{1}{24\epsilon})m$

edges such that

${\rm cr}(G') \geq (\frac{1}{28}-o(1)){\rm cr}(G)$

.

While some research has been performed on the human understanding of static graph layout algorithms, dynamic graph layout algorithms have only recently been developed sufficiently to enable similar investigations. This paper presents the first empirical analysis of a dynamic graph layout algorithm, focusing on the assumption that maintaining the “mental map” between time-slices assists with the comprehension of the evolving graph. The results confirm this assumption with respect to some categories of tasks.

Consider a geometric graph

G

, drawn with straight lines in the plane. For every pair

a

,

b

of vertices of

G

, we compare the shortest-path distance between

a

and

b

in

G

(with Euclidean edge lengths) to their actual Euclidean distance in the plane. The worst-case ratio of these two values, for all pairs of vertices, is called the vertex-to-vertex

dilation

of

G

.

We prove that computing a minimum-dilation graph that connects a given

n

-point set in the plane, using not more than a given number

m

of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. In addition, we show that the minimum dilation tree over a given point set may in fact contain edge crossings.

We investigate which chordal graphs have a representation as intersection graphs of pseudosegments. The main contribution is a construction which shows that all chordal graphs which have a representation as intersection graph of subpaths on a tree are representable. A family of intersection graphs of substars of a star is used to show that not all chordal graphs are representable by pseudosegments.

st

-orientations (

st

-numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. Several algorithms have been proposed in the past to compute an

st

-orientation of a biconnected graph. However, as indicated in [1], the computation of more than one

st

-orientation is very important for many applications in multiple research areas, such as this of Graph Drawing. In this paper we show how to compute such orientations with certain (parameterized) characteristics in the final

st

-oriented graph, such as the length of the longest path. Apart from Graph Drawing, this work applies in other areas such as Network Routing and in tackling difficult problems such as Graph Coloring and Longest Path. We present primary approaches to the problem of computing longest path parameterized

st

-orientations of graphs, an analytical presentation (together with proof of correctness) of a new

O

(

m

log

5

n

) (

O

(

m

log

n

) for planar graphs) time algorithm that computes such orientations (and which was used in [1]) and extensive computational results that reveal the robustness of the algorithm.

This article introduces a straight-line drawing algorithm for quadrangulations, in the family of the face-counting algorithms. It outputs in linear time a drawing on a regular

W

×

H

grid such that

W

 + 

H

 = 

n

 − 1 − 

Δ

, where

n

is the number of vertices and

Δ

is an explicit combinatorial parameter of the quadrangulation.

The need to visualize large and complex networks has strongly increased in the last decade. Although networks with more than 1000 vertices seem to be prohibitive for a comprehensive layout, real-world networks exhibit a very inhomogenous edge density that can be harnessed to derive an aesthetic and structured layout. Here, we will present a heuristic that finds a spanning tree with a very low average spanner property for the non-tree edges, the so-called

backbone

of a network. This backbone can then be used to apply a modified tree-layout algorithm to draw the whole graph in a way that highlights dense parts of the graph, so-called clusters, and their inter-connections.

In this paper we consider the problem of creating partitioned drawings of graphs. In a partitioned drawing each vertex is placed inside a given partition cell of a rectangular partition of the drawing area. This problem has several applications in practice, e.g. for UML activity diagrams or wiring schematics. We first formalize the problem and analyze its complexity. Then we give a heuristic approach which is based on the topology-shape-metrics approach and produces partitioned drawings in time

O

((|

V

| + 

c

)

2

log(|

V

| + 

c

)), where

c

denotes the number of crossings.

We investigate the problem of creating simplified representations of polygonal paths. Specifically, we look at a path simplification problem in which line segments of a simplification are required to conform with a restricted set of directions

${\cal C}$

. An algorithm is given to compute such simplified paths in

$\O(|{\cal C}|^3 n^2)$

time, where

n

is the number of vertices in the original path. This result is extended to produce an algorithm for graphs induced by multiple intersecting paths. The algorithm is applied to construct schematised representations of real world railway networks, in the style of metro maps.

In this paper we consider a new problem that occurs when drawing wiring diagrams or public transportation networks. Given an embedded graph

G

 = (

V

,

E

) (e.g., the streets served by a bus network) and a set

L

of paths in

G

(e.g., the bus lines), we want to draw the paths along the edges of

G

such that they cross each other as few times as possible. For esthetic reasons we insist that the relative order of the paths that traverse a node does not change within the area occupied by that node.

Our main contribution is an algorithm that minimizes the number of crossings on a single edge {

u

,

v

} ∈ 

E

if we are given the order of the incoming and outgoing paths. The difficulty is deciding the order of the paths that terminate in

u

or

v

with respect to the fixed order of the paths that do not end there. Our algorithm uses dynamic programming and takes

O

(

n

2

) time, where

n

is the number of terminating paths.

We consider graph drawing algorithms for learning spaces, a type of

st

-oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any

st

-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an

st

-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant.

Graph drawing research traditionally focuses on producing geometric embeddings of graphs satisfying various aesthetic constraints. After the geometric embedding is specified, there is an additional step that is often overlooked or ignored: assigning display colors to the graph’s vertices. We study the additional aesthetic criterion of assigning distinct colors to vertices of a geometric graph so that the colors assigned to adjacent vertices are as different from one another as possible. We formulate this as a problem involving perceptual metrics in color space and we develop algorithms for solving this problem by embedding the graph in color space. We also present an application of this work to a distributed load-balancing visualization problem.

We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and intersection-free morph between two sphere drawings of a maximally planar graph, provided that both sphere drawings have convex inscribed polytopes, where sphere drawings are the spherical equivalent of plane drawings: intersection-free geodesic-arc drawings. In addition, we describe a morphing algorithm along with its implementation. Movies of sample morphs can be found at

http://www.cs.arizona.edu/~mlandis/smorph

.

This paper addresses the problem of designing drawing algorithms that receive as input a planar graph

G

, a partitioning of the vertices of

G

into

k

different semantic categories

V

0

, ⋯ ,

V

k

 − 1

, and

k

disjoint sets

S

0

, ⋯ ,

S

k

 − 1

of points in the plane with |

V

i

| = |

S

i

| (

i

 ∈ {0, ⋯ ,

k

 − 1}). The desired output is a planar drawing such that the vertices of

V

i

are mapped onto the points of

S

i

and such that the curve complexity of the edges (i.e. the number of bends along each edge) is kept small. Particular attention is devoted to outerplanar graphs, for which lower and upper bounds on the number of bends in the drawings are established.

Bar

k

-visibility graphs are graphs admitting a representation in which the vertices correspond to horizontal line segments, called bars, and the edges correspond to vertical lines of sight which can traverse up to

k

bars. These graphs were introduced by Dean et al. [3] who conjectured that bar 1-visibility graphs have thickness at most 2. We construct a bar 1-visibility graph having thickness 3, disproving their conjecture. For a special case of bar 1-visibility graphs we present an algorithm partitioning the edges into two plane graphs, showing that for this class the thickness is indeed bounded by 2.

The Kandinsky model has been introduced by Fößmeier and Kaufmann in order to deal with planar orthogonal drawings of planar graphs with maximal vertex degree higher than four [7]. No polynomial-time algorithm is known for computing a (region preserving) bend minimal Kandinsky drawing. In this paper we suggest a new 2-approximation algorithm for this problem. Our extensive computational experiments [13] show that the quality of the computed solutions is better than those of its predecessors [6]. E.g., for all instances in the Rome graph benchmark library [4] it computed the optimal solution, and for randomly generated triangulated graphs with up to 800 vertices, the absolute error was less than 2 on average.

This paper studies how to compute radial drawings of graphs by taking into account additional geometric constraints which correspond to typical aesthetic and semantic requirements for the visualization. The following requirements are considered: vertex centrality, edge crossings, curve complexity, and vertex radial distribution. Trade-offs among these requirements and efficient drawing algorithms are presented.

Consider a graph

G

drawn in the plane so that each vertex lies on a distinct horizontal line ℓ

j

 = {(

x

,

j

) |

x

 ∈ ℝ}. The bijection

φ

that maps the set of

n

vertices

V

to a set of distinct horizontal lines ℓ

j

forms a

labeling

of the vertices. Such a graph

G

with the labeling

φ

is called an

n-level graph

and is said to be

n-level planar

if it can be drawn with straight-line edges and no crossings while keeping each vertex on its own level. In this paper, we consider the class of trees that are

n

-level planar regardless of their labeling. We call such trees

unlabeled level planar

(

$\sf{ULP}$

). Our contributions are three-fold. First, we provide a complete characterization of

$\sf{ULP}$

trees in terms of a pair of forbidden subtrees. Second, we show how to draw

$\sf{ULP}$

trees in linear time. Third, we provide a linear time recognition algorithm for

$\sf{ULP}$

trees.

Let

G

be a bipartite graph, and let

λ

e

,

λ

i

be two parallel convex curves; we study the question about whether

G

admits a planar straight line drawing such that the vertices of one partite set of

G

lie on

λ

e

and the vertices of the other partite set lie on

λ

i

. A characterization is presented that gives rise to linear time testing and drawing algorithms.

Circular graph layout is a drawing scheme where all nodes are placed on the perimeter of a circle. An inherent issue with circular layouts is that the rigid restriction on node placement often gives rise to long edges and an overall dense drawing. We suggest here three independent, complementary techniques for lowering the density and improving the readability of circular layouts. First, a new algorithm is given for placing the nodes on the circle such that edge lengths are reduced. Second, we enhance the circular drawing style by allowing some of the edges to be routed around the exterior of the circle. This is accomplished with an algorithm for optimally selecting such a set of externally routed edges. The third technique reduces density by coupling groups of edges as bundled splines that share part of their route. Together, these techniques are able to reduce clutter, density and crossings compared with existing methods.

Node-link diagrams are widely used in information visualization to show relationships among data. However, when the size of data becomes very large, node-link diagrams will become cluttered and visually confusing for users. In this paper, we propose a novel controllable edge clustering method based on Delaunay triangulation to reduce visual clutter for node-link diagrams. Our method uses curves instead of straight lines to represent links and these curves can be grouped together according to their relative positions and directions. We further introduce progressive edge clustering to achieve continuous level-of-details for large networks.

Confluent drawing is a technique that allows some non-planar graphs to be visualized in a planar way. This approach merges edges together, drawing groups of them as single

tracks

, similar to train tracks. In the general case, producing confluent drawings automatically has proven quite difficult. We introduce the biclique edge cover graph that represents a graph

G

as an interconnected set of cliques and bicliques. We do this in such a way as to permit a straightforward transformation to a confluent drawing of

G

. Our result is a new sufficient condition for confluent planarity and an additional algorithmic approach for generating confluent drawings. We give some experimental results gauging the performance of existing confluent drawing heuristics.

In this paper we study connections between Schnyder woods and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and dimension theory. Orthogonal surfaces explain the connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says that the face lattice of a 3-polytope minus one face has dimension three. Our proof yields a companion linear time algorithm for the construction of the three linear orders that realize the face lattice.

Coplanar orthogonal surfaces are in correspondance with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder’s face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time.

In this paper, we study the

k

-

tree partition problem

which is a partition of the set of edges of a graph into

k

edge-disjoint trees. This problem occurs at several places with applications e.g. in network reliability and graph theory. In graph drawing there is the still unbeaten (

n

 − 2) ×(

n

 − 2) area planar straight line drawing of maximal planar graphs using Schnyder’s realizers [15], which are a 3-tree partition of the inner edges. Maximal planar bipartite graphs have a 2-tree partition, as shown by Ringel [14]. Here we give a different proof of this result with a linear time algorithm. The algorithm makes use of a new ordering which is of interest of its own. Then we establish the NP-hardness of the

k

-tree partition problem for general graphs and

k

 ≥ 2. This parallels NP-hard partition problems for the vertices [3], but it contrasts the efficient computation of partitions into forests (also known as arboricity) by matroid techniques [7].

Graph drawing software are now commonly used. However, the choice of a well-adapted program may be hard for an inexperienced user. This poster presents a website (http://www.polytech.univ-nantes.fr/GVSR/) built to help users choose a program adapted to their problems. So far, this site uniformely presents fifty programs and aims at helping users both in their choices and in comparing the programs.

We demonstrate a collection of techniques that seek to make the transition between drawings based on two topologically distinct spanning trees of the same graph as clear as possible.

Our recent paper [1] details an algorithm for removing overlap between rectangles, while attempting to displace the rectangles by as little as possible. The algorithm is primarily motivated by the node-overlap removal problem in graph drawing.

This report describes the Thirteenth Annual Graph Drawing Contest, held in conjunction with the 2006 Graph Drawing Symposium in Karlsruhe, Germany. The purpose of the contest is to monitor and challenge the current state of the graph-drawing technology.