Graph Drawing

We consider graphs that admit polyline drawings where all crossings occur at the same angle

$\alpha\in (0,\frac{\pi}{2}]$

. We prove that every graph on

n

vertices that admits such a polyline drawing with at most two bends per edge has

O

(

n

) edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest.

We study a new standard for visualizing graphs: A monotone drawing is a straight-line drawing such that, for every pair of vertices, there exists a path that monotonically increases with respect to some direction. We show algorithms for constructing monotone planar drawings of trees and biconnected planar graphs, we study the interplay between monotonicity, planarity, and convexity, and we outline a number of open problems and future research directions.

We study the problem of characterizing the directed graphs with an upward straight-line embedding into every point set in general or in convex position. We solve two questions posed by Binucci

et al.

[

Computational Geometry: Theory and Applications, 2010

]. Namely, we prove that the classes of directed graphs with an upward straight-line embedding into every point set in convex position and with an upward straight-line embedding into every point set in general position do not coincide, and we prove that every directed caterpillar admits an upward straight-line embedding into every point set in convex position. Further, we provide new partial positive results on the problem of constructing upward straight-line embeddings of directed paths into point sets in general position.

Two graphs

G

1

 = (

V

,

E

1

) and

G

2

 = (

V

,

E

2

) admit a geometric simultaneous embedding if there exists a set of points

P

and a bijection

M

:

P

→

V

that induce planar straight-line embeddings both for

G

1

and for

G

2

. The most prominent problem in this area is the question whether a tree and a path can always be simultaneously embedded. We answer this question in the negative by providing a counterexample. Additionally, since the counterexample uses disjoint edge sets for the two graphs, we also prove that it is not always possible to simultaneously embed two edge-disjoint trees. Finally, we study the same problem when some constraints on the tree are imposed. Namely, we show that a tree of height 2 and a path always admit a geometric simultaneous embedding. In fact, such a strong constraint is not so far from closing the gap with the instances not admitting any solution, as the tree used in our counterexample has height 4.

Difference maps are one way to show changes between timeslices in a dynamic graph. They highlight, using colour, the nodes and edges that were added, removed, or persisted between every pair of adjacent timeslices. Although some work has used difference maps for visualization, no user study has been performed to gauge their performance. In this paper, we present a user study to evaluate the effectiveness of difference maps in comparison with presenting the evolution of the dynamic graph over time on three interfaces. We found evidence that difference maps produced significantly fewer errors when determining the number of edges inserted or removed from a graph as it evolves over time. Also, difference maps were significantly preferred on all tasks.

A major factor affecting the readability of a graph drawing is its resolution. In the graph drawing literature, the resolution of a drawing is either measured based on the angles formed by consecutive edges incident to a common node (angular resolution) or by the angles formed at edge crossings (crossing resolution). In this paper, we evaluate both by introducing the notion of “total resolution”, that is, the minimum of the angular and crossing resolution. To the best of our knowledge, this is the first time where the problem of maximizing the total resolution of a drawing is studied.

The main contribution of the paper consists of drawings of asymptotically optimal total resolution for complete graphs (circular drawings) and for complete bipartite graphs (2-layered drawings). In addition, we present and experimentally evaluate a force-directed based algorithm that constructs drawings of large total resolution.

In stack and queue layouts the vertices of a graph are linearly ordered from left to right, where each edge corresponds to an item and the left and right end vertex of each edge represents the addition and removal of the item to the used data structure. A graph admitting a stack or queue layout is a stack or queue graph, respectively.

Typical stack and queue layouts are rainbows and twists visualizing the LIFO and FIFO principles, respectively. However, in such visualizations, twists cause many crossings, which make the drawings incomprehensible. We introduce linear cylindric layouts as a visualization technique for queue and deque (double-ended queue) graphs. It provides new insights into the characteristics of these fundamental data structures and extends to the visualization of mixed layouts with stacks and queues. Our main result states that a graph is a deque graph if and only if it has a plane linear cylindric drawing.

Applying the multilevel paradigm to energy-based layout algorithms can improve both the quality of the resulting drawings as well as the running time of the layout computation. In order to do this, approaches for the different multilevel phases refinement, placement, layout, and optionally scaling and postprocessing need to be implemented. A number of multilevel layout algorithms have been proposed already, which differ in the way these phases are realized. We present an experimental study that investigates the influence of varying combinations with respect to running time and quality criteria.

In this work we consider the following problem. Given a planar graph

G

with maximum degree 4 and a function flex:

$E \longrightarrow {\mathbb{N}}_0$

that gives each edge a

flexibility

. Does

G

admit a planar embedding on the grid such that each edge

e

has at most flex(

e

) bends? Note that in our setting the combinatorial embedding of

G

is not fixed.

We give a polynomial-time algorithm for this problem when the flexibility of each edge is positive. This includes as a special case the problem of deciding whether

G

admits a drawing with at most one bend per edge.

We explore the complexity of drawing ordered (

k

 − 1)–ary trees on grids with

k

directions for

$k \in \left\{4,6,8\right\}$

and within a given area. This includes, e.g., ternary trees drawn on the orthogonal grid. For aesthetically pleasing tree drawings on these grids, we additionally present various restrictions similar to the common hierarchical case. First, we generalize the

${\mathcal{NP}}$

–hardness of minimal width in hierarchical drawings of ordered trees to (

k

 − 1)–ary trees on

k

–grids and then we generalize the Reingold and Tilford algorithm to

k

–grids.

A regular edge labeling (REL) of an irreducible triangulation

G

uniquely defines a rectangular dual of

G

. Rectangular duals find applications in various areas: as floor plans of electronic chips, in architectural designs, as rectangular cartograms, or as treemaps. An irreducible triangulation can have many RELs and hence many rectangular duals. Depending on the specific application different duals might be desirable. In this paper we consider optimization problems on RELs and show how to find optimal or near-optimal RELs for various quality criteria. Furthermore, we give upper and lower bounds on the number of RELs.

We study the classic graph drawing problem of drawing a planar graph using straight-line edges with a prescribed convex polygon as the outer face. Unlike previous algorithms for this problem, which may produce drawings with exponential area, our method produces drawings with polynomial area. In addition, we allow for collinear points on the boundary, provided such vertices do not create overlapping edges. Thus, we solve an open problem of Duncan

et al.

, which, when combined with their work, implies that we can produce a planar straight-line drawing of a combinatorially-embedded genus-

g

graph with the graph’s canonical polygonal schema drawn as a convex polygonal external face.

Many practical applications for drawing graphs are modeled by directed graphs with domain specific constraints. In this paper, we consider the problem of drawing directed hypergraphs with (and without) port constraints, which cover multiple real-world graph drawing applications like data flow diagrams and electric schematics.

Most existing algorithms for drawing hypergraphs with port constraints are adaptions of the framework originally proposed by Sugiyama et al. in 1981 for simple directed graphs. Recently, a practical approach for upward crossing minimization of directed graphs based on the planarization method was proposed [7]. With respect to the number of arc crossings, it clearly outperforms prior (mostly layering-based) approaches. We show how to adopt this idea for hypergraphs with given port constraints, obtaining an upward-planar representation (UPR) of the input hypergraph where crossings are modeled by dummy nodes.

Furthermore, we present the new problem of computing an orthogonal upward drawing with minimal number of crossings from such an UPR, and show that it can be solved efficiently by providing a simple method.

We present a system for the visualization of relational information on the smartphones. It is implemented on the iPhone and on the Google Android platforms and is based on a new visualization paradigm that poses interesting algorithmic challenges. We also show customizations of the system to explore and visualize popular social networks.

This paper studies the problem of designing graph drawing algorithms that guarantee good trade-offs in terms of number of edge crossings, crossing angle resolution, and geodesic edge tendency. It describes two heuristics designed within the

topology-driven force-directed

framework that combines two classical graph drawing approaches: the force-directed approach and a planarization-based approach (e.g., the topology-shape-metrics approach). An extensive experimental analysis on two different test suites of graphs shows the effectiveness of the proposed solutions for the optimization of some readability metrics.

For a set

S

of

n

lines labeled from 1 to

n

, we say that

S

supports an

n

-vertex planar graph

G

if for every labeling from 1 to

n

of its vertices,

G

has a straight-line crossing-free drawing with each vertex drawn as a point on its associated line. It is known from previous work [4] that no set of

n

parallel lines supports all

n

-vertex planar graphs. We show that intersecting lines, even if they intersect at a common point, are more “powerful” than a set of parallel lines. In particular, we prove that every such set of lines supports outerpaths, lobsters, and squids, none of which are supported by any set of parallel lines. On the negative side, we prove that no set of

n

lines that intersect in a common point supports all

n

-vertex planar graphs. Finally, we show that there exists a set of

n

lines in general position that does not support all

n

-vertex planar graphs.

We study methods for drawing trees with perfect angular resolution, i.e., with angles at each vertex,

v

, equal to 2

π

/

d

(

v

). We show:

1

Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area.

2

There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution.

3

Any ordered tree has a crossing-free

Lombardi-style

drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area.

Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution.

We introduce the notion of Lombardi graph drawings, named after the American abstract artist Mark Lombardi. In these drawings, edges are represented as circular arcs rather than as line segments or polylines, and the vertices have

perfect angular resolution

: the edges are equally spaced around each vertex. We describe algorithms for finding Lombardi drawings of regular graphs, graphs of bounded degeneracy, and certain families of planar graphs.

We show that every graph of maximum degree three can be drawn in three dimensions with at most two bends per edge, and with 120° angles between any two edge segments meeting at a vertex or a bend. We show that every graph of maximum degree four can be drawn in three dimensions with at most three bends per edge, and with 109.5° angles, i.e., the angular resolution of the diamond lattice, between any two edge segments meeting at a vertex or bend.

We show that there exist series-parallel graphs requiring

$\Omega(n 2^{\sqrt{\log n}})$

area in any straight-line or poly-line grid drawing, improving the previously best known Ω(

n

log

n

) lower bound.

A drawing of a graph in the plane is called a

thrackle

if every pair of edges meets precisely once, either at a common vertex or at a proper crossing. Let

t

(

n

) denote the maximum number of edges that a thrackle of

n

vertices can have. According to a 40 years old conjecture of Conway,

t

(

n

) = 

n

for every

n

 ≥ 3. For any

ε

> 0, we give an algorithm terminating in

$e^{O((1/\varepsilon^2)\ln(1/\varepsilon))}$

steps to decide whether

t

(

n

) ≤ (1 + 

ε

)

n

for all

n

 ≥ 3. Using this approach, we improve the best known upper bound,

$t(n)\le \frac 32(n-1)$

, due to Cairns and Nikolayevsky, to

$\frac{167}{117}n<1.428n$

.

An important step in laying out hierarchical network diagrams is to order the nodes on each level. The usual approach is to minimize the number of edge crossings. This problem is NP-hard even for two layers when the first layer is fixed. Hence, in practice crossing minimization is performed using heuristics. Another suggested approach is to maximize the planar subgraph, i.e. find the least number of edges to delete to make the graph planar. Again this is performed using heuristics since minimal edge deletion for planarity is NP-hard. We show that using modern SAT and MIP solving approaches we can find

optimal

orderings for minimal crossing or minimal edge deletion for planarization on reasonably sized graphs. These exact approaches provide a benchmark for measuring quality of heuristic crossing minimization and planarization algorithms. Furthermore, we can straightforwardly extend our approach to minimize crossings followed by maximizing planar subgraph or vice versa; these hybrid approaches produce noticeably better layout then either crossing minimization or planarization alone.

In this paper, we consider the problem of representing graphs by triangles whose sides touch. We present linear time algorithms for creating touching triangles representations for outerplanar graphs, square grid graphs, and hexagonal grid graphs. The class of graphs with touching triangles representations is not closed under minors, making characterization difficult. We do show that pairs of vertices can only have a small common neighborhood, and we present a complete characterization of the subclass of biconnected graphs that can be represented as triangulations of some polygon.

A contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. de Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual.

A primal-dual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge

uv

, bordering faces

f

and

g

, the intersection between the triangles corresponding to

u

and

v

is the same point as the intersection between the triangles corresponding to

f

and

g

. We prove that every 3-connected planar map admits a primal-dual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a node of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps.

We study the

maximum differential graph coloring problem

, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of

k

-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs.

A graph

G

on

n

vertices is a

k

-dot product graph if there are vectors

$u_1, \dots, u_n \in {\mathbb R}^k$

, one for each vertex of

G

, such that

$u_i^T u_j \geq 1$

if and only if

ij

 ∈ 

E

(

G

). Fiduccia, Scheinerman, Trenk and Zito (1998) asked whether every planar graph is a 3-dot product graph. We show that the answer is “no”. On the other hand, every planar graph is a 4-dot product graph.

We settle a problem of Dujmović, Eppstein, Suderman, and Wood by showing that there exists a function

f

with the property that every planar graph

G

with maximum degree

d

admits a drawing with noncrossing straight-line edges, using at most

f

(

d

) different slopes. If we allow the edges to be represented by polygonal paths with

one

bend, then 2

d

slopes suffice. Allowing

two

bends per edge, every planar graph with maximum degree

d

 ≥ 3 can be drawn using segments of at most ⌈

d

/2⌉ different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. These bounds cannot be improved.

We study the complexity of the problem of finding non-planar rectilinear drawings of graphs. This problem is known to be NP-complete. We consider natural restrictions of this problem where constraints are placed on the possible orientations of edges. In particular, we show that if each edge has prescribed direction “left”, “right”, “down” or “up”, the problem of finding a rectilinear drawing is polynomial, while finding such a drawing with the minimum area is NP-complete. When assigned directions are “horizontal” or “vertical” or a cyclic order of the edges at each vertex is specified, the problem is NP-complete. We show that these two NP-complete cases are fixed parameter tractable in the number of vertices of degree 3 or 4.

A straight-line drawing of a plane graph

G

is a planar drawing of

G

, where each vertex is drawn as a point and each edge is drawn as a straight-line segment. Given a set

S

of

n

points on the Euclidean plane, a point-set embedding of a plane graph

G

with

n

vertices on

S

is a straight-line drawing of

G

, where each vertex of

G

is mapped to a distinct point of

S

. The problem of deciding if

G

admits a point-set embedding on

S

is NP-complete in general and even when

G

is 2-connected and 2-outerplanar. In this paper we give an

O

(

n

2

log

n

) time algorithm to decide whether a plane 3-tree admits a point-set embedding on a given set of points or not, and find an embedding if it exists. We prove an Ω(

n

log

n

) lower bound on the time complexity for finding a point-set embedding of a plane 3-tree. Moreover, we consider a variant of the problem where we are given a plane 3-tree

G

with

n

vertices and a set

S

of

k

 > 

n

points, and give a polynomial time algorithm to find a point-set embedding of

G

on

S

if it exists.

We show how to improve the Sugiyama scheme by edge bundling. Our method modifies the layout produced by the Sugiyama scheme by bundling some of the edges together. The bundles are created by a new algorithm based on minimizing the total ink needed to draw the graph edges. We give several implementations that vary in quality of the resulting layout and execution time. To diminish the number of edge crossings inside of the bundles we apply a metro-line crossing minimization technique. The method preserves the Sugiyama style of the layout and creates a more readable view of the graph.

The need of effective drawings for non-planar dense graphs is motivated by the wealth of applications in which they occur, including social network analysis, security visualization and web clustering engines, just to name a few. One common issue graph drawings are affected by is the visual clutter due to the high number of (possibly intersecting) edges to display. Confluent drawings address this problem by bundling groups of edges sharing the same path, resulting in a representation with less edges and no edge intersections. In this paper we describe how to create a confluent drawing of a graph from its rectangular dual and we show two important advantages of this approach.

Presented here are necessary and sufficient conditions for a cubic graph equipped with a Tait-coloring to have a drawing in the real projective plane where every edge is represented by a line segment, all of the lines supporting the edges sharing a common color are concurrent, and all of the supporting lines are distinct.

Let

R

and

B

be two sets of distinct points such that the points of

R

are coloured red and the points of

B

are coloured blue. Let

$\cal G$

be a family of planar graphs such that for each graph in the family |

R

| vertices are red and |

B

| vertices are blue. The set

R

 ∪ 

B

is a universal pointset for

$\cal G$

if every graph

$G \in \cal G$

has a straight-line planar drawing such that the blue vertices of

G

are mapped to the points of

B

and the red vertices of

G

are mapped to the points of

R

. In this paper we describe universal pointsets for meaningful classes of 2-coloured trees and show applications of these results to the coloured simultaneous geometric embeddability problem.

We study how much better a right-angled crossing (RAC) drawing of a planar graph can be than any planar drawing of the same planar graph. We analyze the area requirement, the edge-length ratio, and the angular resolution. For the first two measures, a RAC drawing can be arbitrarily much better, whereas for the third measure a RAC drawing can be 2.75 times as good.

Geometric intersection graphs are graphs determined by intersections of geometric objects. We study the complexity of visualizing the arrangements of objects that induce such graphs. We give a general framework for describing geometric intersection graphs, using arbitrary finite base sets of rationally given convex polygons and affine transformations. We prove that for every class of intersection graphs that fits the framework, the graphs in the class have a representation using polynomially many bits. Consequently, the recognition problem of these classes is in NP (and thus NP-complete). We also give an algorithm to find a drawing of the objects in the plane, if a graph class fits the framework.

Graphs are an accepted and popular way of representing and solving problems of various kinds. Thus, applications of graphs as well as related topics such as graph visualization and graph representation are numerous. Our application is located in the domain of industrial automation and driven by the need of parallelizing our controller’s firmware for the upcoming multi-core CPUs. As efficiency matters, we thereby aim at gaining maximum performance increases by spending no more implementation effort than necessary. In order to achieve that objective, we at first want to explore, evaluate and visualize those efficient parallelization alternatives by means of a graph-based model of our firmware. Thus, we are currently developing the

EEEPA (

E

xploration and

E

valuation of

E

fficient

P

arallelization

A

lternatives)

tool for this purpose. Thereby, we have chosen and extended

GraphML

[1], a widespread format for graph representation.

Generating route sketches is a graph redrawing problem, where we are given an initial drawing of a graph

G

and want to find a new,

schematized

drawing of

G

that reduces the drawing complexity while preserving the structural characteristics of the input. The motivation of our work is the visualization of routes in road networks as sketches for driving directions. An important property of a route sketch is that it focuses on road changes and important landmarks rather than exact geography and distances. Typically the start and destination lie in populated areas that are locally reached via a sequence of relatively short road segments. On the other hand, the majority of the route typically consists of long highway segments with no or only few road changes. This property makes it difficult to display driving directions for the whole route in a single traditional map since some areas require much smaller scales than others. The strength of route sketches for this purpose is that they are not drawn to scale but rather use space proportionally to the route complexity.

When working with graphs one often faces the problem of comparing two or more graphs. For example in biology, when two protein-protein interaction networks from closely related species have to be compared, the graphs can easily contain several hundred nodes and thousands of edges but very few differences. Our goal was to develop a software-tool that creates an overview of large graphs and maintains the structure but reduces the number of nodes and edges and enables the user to easily find and investigate the areas of interest. This problem has been considered in the past by various groups ([1], [2]) and different heuristics have been proposed. Here, we follow the concept proposed in [3]. For this work, we assume that the input-graphs are relatively large with small local differences and node correspondences are known.

In this paper we investigate how one can modify an orthogonal graph drawing to accommodate the placement of overlap-free labels with the minimum cost. We present a polynomial time algorithm that finds the minimum increase of space in one direction, needed to resolve overlaps, while preserving the orthogonal representation of the drawing.

Recent empirical research has shown that increasing the angle of crossings reduces the effect of crossings and improves human readability [5]. In this paper, we introduce a post-processing algorithm, namely MAXCIR, that aims to increase crossing angles of circular layouts by using Quadratic Programming. Experimental results indicate that our method significantly increases crossing angles compared to the traditional equal-spacing algorithm, and that the running time is fairly negligible.

It is easy to find graph visualization applications for all sorts of uses. However, choosing an appropriate application may be difficult. This poster presents a website (

http://gvsr.polytech.univ-nantes.fr/

) built to help users to choose a program adapted to their problems. So far, this site references eighty programs and aims at helping users both in their choices and in comparing the programs. The site is also designed as a tool repository helping the community to access and compare the available tools, and benchmark new techniques and algorithms.

Visualization components from IBM provide a comprehensive set of graphics products for creating highly graphical, interactive displays, including diagrams, gantt charts, maps, business dashboards, business charts, telecom displays, SCADA/HMI Screens and many more. User interface developers reduce development risks and implementation time when deploying the IBM visualization technology. The components are available for many different platforms: various C++ platforms, Java Swing applications, Java Eclipse plugins, thin client AJAX applications, for the Microsoft .NET and the Adobe Flex platform.

Voice portals are widely used to guide users interactively through an application. Recent portals provide a growing number of functions in one application, thus increasing their complexity. This work presents flow-map-based techniques for the comparative visualization of user flows at different time frames, in order to enable dialog designers to analyze and improve the user interaction with these systems.

Natural Language Systems in Voice Portals:

More sophisticated voice portals use natural language systems (NLS), giving users the option to actually “talk” to the system in whole sentences. The system tries to interpret these sentences and interactively asks the user for detailed information, if necessary. Portals using NLS are rather large and complex, making it difficult to analyze their performance. Especially after applying changes to a voice portal or in case of technical problems, it is important to be able to analyze the consequences on user flows in the system.

This report describes the

$17^{\mbox{\scriptsize th}}$

Annual Graph Drawing Contest, held in conjunction with the 2010 Graph Drawing Symposium in Konstanz, Germany. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology.