Skip to main content
main-content

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 21st International Symposium on Graph Drawing, GD 2013, held in Bordeaux, France, in September 2013. The 42 revised full papers presented together with 12 revised short papers, 3 invited talks and 1 poster description were carefully reviewed and selected from 110 submissions. The papers are organized in topical sections on upward drawings, planarity, beyond planarity, geometric representations, 3D et al., universality, practical graph drawing, subgraphs, crossings, geometric graphs and geographic networks, angular restrictions, grids, curves and routes. The book also contains a short description of the graph drawing contest.

Inhaltsverzeichnis

Frontmatter

Upward Drawings

On the Upward Planarity of Mixed Plane Graphs

A

mixed plane graph

is a plane graph whose edge set is partitioned into a set of directed edges and a set of undirected edges. An

orientation

of a mixed plane graph

G

is an assignment of directions to the undirected edges of

G

resulting in a directed plane graph

$\vec G$

. In this paper, we study the computational complexity of testing whether a given mixed plane graph

G

is

upward planar

, i.e., whether it admits an orientation resulting in a directed plane graph

G

such that

G

admits a planar drawing in which each edge is represented by a curve monotonically increasing in the

y

-direction according to its orientation.

Our contribution is threefold. First, we show that the upward planarity testing problem is solvable in cubic time for

mixed outerplane graphs

. Second, we show that the problem of testing the upward planarity of mixed plane graphs reduces in quadratic time to the problem of testing the upward planarity of

mixed plane triangulations

. Third, we exhibit linear-time testing algorithms for two classes of mixed plane triangulations, namely

mixed plane

3

-trees

and mixed plane triangulations in which

the undirected edges induce a forest

.

Fabrizio Frati, Michael Kaufmann, János Pach, Csaba D. Tóth, David R. Wood

Upward Planarity Testing: A Computational Study

A directed acyclic graph (DAG) is

upward planar

if it can be drawn without any crossings while all edges—when following them in their direction—are drawn with strictly monotonously increasing

y

-coordinates. Testing whether a graph allows such a drawing is known to be NP-complete, but there is a substantial collection of different algorithmic approaches known in literature.

In this paper, we give an overview of the known algorithms, ranging from combinatorial FPT and branch-and-bound algorithms to ILP and SAT formulations. Most approaches of the first class have only been considered from the theoretical point of view, but have never been implemented. For the first time, we give an extensive experimental comparison between virtually all known approaches to the problem.

Furthermore, we present a new SAT formulation based on a recent theoretical result by Fulek et al. [8], which turns out to perform best among all known algorithms.

Markus Chimani, Robert Zeranski

Planarity

Characterizing Planarity by the Splittable Deque

A

graph layout

describes the processing of a graph

G

by a data structure

$\mathcal{D}$

, and the graph is called a

$\mathcal{D}$

-graph. The vertices of

G

are totally ordered in a

linear layout

and the edges are stored and organized in

$\mathcal{D}$

. At each vertex, all edges to predecessors in the linear layout are removed and all edges to successors are inserted. There are intriguing relationships between well-known data structures and classes of planar graphs: The stack graphs are the outerplanar graphs [4], the queue graphs are the arched leveled-planar graphs [12], the 2-stack graphs are the subgraphs of planar graphs with a Hamilton cycle [4], and the deque graphs are the subgraphs of planar graphs with a Hamilton path [2]. All of these are proper subclasses of the planar graphs, even for maximal planar graphs.

We introduce

splittable deques

as a data structure to capture planarity. A splittable deque is a deque which can be split into sub-deques. The splittable deque provides a new insight into planarity testing by a game on switching trains. Here, we use it for a linear-time planarity test of a given rotation system.

Christopher Auer, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer

Strip Planarity Testing

In this paper we introduce and study the

strip planarity testing

problem, which takes as an input a planar graph

G

(

V

,

E

) and a function

γ

:

V

 → {1,2,…,

k

} and asks whether a planar drawing of

G

exists such that each edge is monotone in the

y

-direction and, for any

u

,

v

 ∈ 

V

with

γ

(

u

) < 

γ

(

v

), it holds

y

(

u

) < 

y

(

v

). The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as

clustered planarity

,

upward planarity

, and

level planarity

. We show that the problem is polynomial-time solvable if

G

has a fixed planar embedding.

Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati

Morphing Planar Graph Drawings Efficiently

A morph between two straight-line planar drawings of the same graph is a continuous transformation from the first to the second drawing such that planarity is preserved at all times. Each step of the morph moves each vertex at constant speed along a straight line. Although the existence of a morph between any two drawings was established several decades ago, only recently it has been proved that a polynomial number of steps suffices to morph any two planar straight-line drawings. Namely, at SODA 2013, Alamdari

et al.

[1] proved that any two planar straight-line drawings of a planar graph can be morphed in

O

(

n

4

) steps, while

O

(

n

2

) steps suffice if we restrict to maximal planar graphs.

In this paper, we improve upon such results, by showing an algorithm to morph any two planar straight-line drawings of a planar graph in

O

(

n

2

) steps; further, we show that a morph with

O

(

n

) steps exists between any two planar straight-line drawings of a series-parallel graph.

Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli

Invited Talk

Graph Drawing through the Lens of a Framework for Analyzing Visualization Methods

(Invited Talk, Extended Abstract)

The visualization community has drawn heavily on the algorithmic and systems-building work that has appeared with the graph drawing literature, and in turn has been a fertile source of applications. In the spirit of further promoting the effective transfer of ideas between our two communities, I will discuss a framework for analyzing the design of visualization systems. I will then analyze a range of graph drawing techniques through this lens. In the early stages of a project, this sort of analysis may benefit algorithm developers who seek to identify open problems to attack. In later project stages, it could guide algorithm developers in characterizing how newly developed layout methods connect with the tasks and goals of target users in different application domains.

Tamara Munzner

Beyond Planarity

A Linear-Time Algorithm for Testing Outer-1-Planarity

A graph is

1-planar

if it can be embedded in the plane with at most one crossing per edge. A graph is

outer-1-planar

if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists.

Seok-Hee Hong, Peter Eades, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer, Yusuke Suzuki

Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. In general, 1-planar graphs do not admit straight-line drawings. We show that every 3-connected 1-planar graph has a straight-line drawing on an integer grid of quadratic size, with the exception of a single edge on the outer face that has one bend. The drawing can be computed in linear time from any given 1-planar embedding of the graph.

Md. Jawaherul Alam, Franz J. Brandenburg, Stephen G. Kobourov

New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs

A topological graph is

k-quasi-planar

if it does not contain

k

pairwise crossing edges. An old conjecture states that for every fixed

k

, the maximum number of edges in a

k

-quasi-planar graph on

n

vertices is

O

(

n

). Fox and Pach showed that every

k

-quasi-planar graph with

n

vertices and no pair of edges intersecting in more than

O

(1) points has at most

n

(log

n

)

O

(log

k

)

edges. We improve this upper bound to

$2^{\alpha(n)^c}n\log n$

, where

α

(

n

) denotes the inverse Ackermann function, and

c

depends only on

k

. We also show that every

k

-quasi-planar graph with

n

vertices and every two edges have at most one point in common has at most

O

(

n

log

n

) edges. This improves the previously known upper bound of

$2^{\alpha(n)^c}n\log n$

obtained by Fox, Pach, and Suk.

Andrew Suk, Bartosz Walczak

Recognizing Outer 1-Planar Graphs in Linear Time

A graph is outer 1-planar (

o1p

) if it can be drawn in the plane such that all vertices are on the outer face and each edge is crossed at most once.

o1p

graphs generalize outerplanar graphs, which can be recognized in linear time and specialize 1-planar graphs, whose recognition is

$\mathcal{NP}$

-hard.

Our main result is a linear-time algorithm that first tests whether a graph

G

is

o1p

, and then computes an embedding. Moreover, the algorithm can augment

G

to a maximal

o1p

graph. If

G

is not

o1p

, then it includes one of six minors (see Fig. 3), which are also detected by the recognition algorithm. Hence, the algorithm returns a positive or negative witness for

o1p

.

Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber

Geometric Representations

Straight Line Triangle Representations

A straight line triangle representation (SLTR) of a planar graph is a straight line drawing such that all the faces including the outer face have triangular shape. Such a drawing can be viewed as a tiling of a triangle using triangles with the input graph as skeletal structure. In this paper we present a characterization of graphs that have an SLTR that is based on flat angle assignments, i.e., selections of angles of the graph that have size

π

in the representation. We also provide a second characterization in terms of contact systems of pseudosegments. With the aid of discrete harmonic functions we show that contact systems of pseudosegments that respect certain conditions are stretchable. The stretching procedure is then used to get straight line triangle representations. Since the discrete harmonic function approach is quite flexible it allows further applications, we mention some of them.

The drawback of the characterization of SLTRs is that we are not able to effectively check whether a given graph admits a flat angle assignment that fulfills the conditions. Hence it is still open to decide whether the recognition of graphs that admit straight line triangle representation is polynomially tractable.

Nieke Aerts, Stefan Felsner

Extending Partial Representations of Circle Graphs

The partial representation extension problem

is a recently introduced generalization of the recognition problem. A

circle graph

is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph

G

and a partial representation

$\mathcal{R'}$

giving some pre-drawn chords that represent an induced subgraph of

G

. The question is whether one can extend

$\mathcal{R'}$

to a representation

$\mathcal{R}$

of the entire

G

, i.e., whether one can draw the remaining chords into a partially pre-drawn representation.

Our main result is a polynomial-time algorithm for partial representation extension of circle graphs. To show this, we describe the structure of all representation a circle graph based on split decomposition. This can be of an independent interest.

Steven Chaplick, Radoslav Fulek, Pavel Klavík

On Balanced -Contact Representations

In a

-contact representation of a planar graph

G

, each vertex is represented as an axis-aligned plus shape consisting of two intersecting line segments (or equivalently, four axis-aligned line segments that share a common endpoint), and two plus shapes touch if and only if their corresponding vertices are adjacent in

G

. Let the four line segments of a plus shape be its arms. In a

c

-balanced representation,

c

 ≤ 1, every arm can touch at most

$\lceil c\varDelta\rceil$

other arms, where

$\varDelta$

is the maximum degree of

G

. The widely studied

T

- and

L

-contact representations are

c

-balanced representations, where

c

could be as large as 1. In contrast, the goal in a

c

-balanced representation is to minimize

c

. Let

c

k

, where

k

 ∈ {2,3}, be the smallest

c

such that every planar

k

-tree has a

c

-balanced representation. In this paper we show that 1/4 ≤ 

c

2

 ≤ 1/3 ( = 

b

2

) and 1/3 < 

c

3

 ≤ 1/2 ( = 

b

3

). Our result has several consequences. Firstly, planar

k

-trees admit 1-bend box-orthogonal drawings with boxes of size

$\lceil b_k\varDelta\rceil \times \lceil b_k\varDelta\rceil$

, which generalizes a result of Tayu, Nomura, and Ueno. Secondly, they admit 1-bend polyline drawings with

$2\lceil b_k\varDelta\rceil$

slopes, which is significantly smaller than the

$2\varDelta$

upper bound established by Keszegh, Pach, and Pálvölgyi for arbitrary planar graphs.

Stephane Durocher, Debajyoti Mondal

Strongly-Connected Outerplanar Graphs with Proper Touching Triangle Representations

A

proper touching triangle representation

$\mathcal{R}$

of an

n

-vertex planar graph consists of a triangle divided into

n

non-overlapping triangles. A pair of triangles are considered to be adjacent if they share a partial side of positive length. Each triangle in

$\mathcal{R}$

represents a vertex, while each pair of adjacent triangles represents an edge in the planar graph. We consider the problem of determining when a proper touching triangle representation exists for a

strongly-connected outerplanar graph

, which is biconnected and after the removal of all degree-2 vertices and outeredges, the resulting

connected

subgraph only has chord edges (w.r.t. the original graph). We show that such a graph has a proper representation if and only if the graph has at most two

internal faces

(

i.e.,

faces with no outeredges).

J. Joseph Fowler

3D et al.

Achieving Good Angular Resolution in 3D Arc Diagrams

We study a three-dimensional analogue to the well-known graph visualization approach known as

arc diagrams

. We provide several algorithms that achieve good angular resolution for 3D arc diagrams, even for cases when the arcs must project to a given 2D straight-line drawing of the input graph. Our methods make use of various graph coloring algorithms, including an algorithm for a new coloring problem, which we call

localized edge coloring

.

Michael T. Goodrich, Paweł Pszona

A Duality Transform for Constructing Small Grid Embeddings of 3D Polytopes

We study the problem of how to obtain an integer realization of a 3d polytope when an integer realization of its dual polytope is given. We focus on grid embeddings with small coordinates and develop novel techniques based on Colin de Verdière matrices and the Maxwell–Cremona lifting method.

As our main result we show that every truncated 3d polytope with

n

vertices can be realized on a grid of size polynomial in

n

. Moreover, for a class

$\mathcal{C}$

of simplicial 3d polytopes with bounded vertex degree, at least one vertex of degree 3, and polynomial size grid embedding, the dual polytopes of

$\mathcal{C}$

can be realized on a polynomial size grid as well.

Alexander Igamberdiev, André Schulz

Block Additivity of ℤ2-Embeddings

We study embeddings of graphs in surfaces up to ℤ

2

-homology. We introduce a notion of genus mod 2 and show that some basic results, most noteworthy block additivity, hold for ℤ

2

-genus. This has consequences for (potential) Hanani-Tutte theorems on arbitrary surfaces.

Marcus Schaefer, Daniel Štefankovič

Universality

Exploiting Air-Pressure to Map Floorplans on Point Sets

We prove a conjecture of Ackerman, Barequet and Pinter. Every floorplan with

n

segments can be embedded on every set of

n

points in generic position. The construction makes use of area universal floorplans also known as area universal rectangular layouts.

The notion of area used in our context depends on a nonuniform density function. We, therefore, have to generalize the theory of area universal floorplans to this situation. The method is then used to prove a result about accommodating points in floorplans that is slightly more general than the conjecture of Ackerman et al.

Stefan Felsner

Superpatterns and Universal Point Sets

An old open problem in graph drawing asks for the size of a

universal point set

, a set of points that can be used as vertices for straight-line drawings of all

n

-vertex planar graphs. We connect this problem to the theory of permutation patterns, where another open problem concerns the size of

superpatterns

, permutations that contain all patterns of a given size. We generalize superpatterns to classes of permutations determined by forbidden patterns, and we construct superpatterns of size

n

2

/4 + Θ(

n

) for the 213-avoiding permutations, half the size of known superpatterns for unconstrained permutations. We use our superpatterns to construct universal point sets of size

n

2

/4 − Θ(

n

), smaller than the previous bound by a 9/16 factor. We prove that every proper subclass of the 213-avoiding permutations has superpatterns of size

O

(

n

log

O

(1)

n

), which we use to prove that the planar graphs of bounded pathwidth have near-linear universal point sets.

Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, David Eppstein

Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices

A simultaneous embedding of two graphs

$G^{\mbox{\textcircled{1}}}$

and

$G^{\mbox{\textcircled{2}}}$

with common graph

$G=G^{\mbox{\textcircled{1}}} \cap G^{\mbox{\textcircled{2}}}$

is a pair of planar drawings of

$G^{\mbox{\textcircled{1}}}$

and

$G^{\mbox{\textcircled{2}}}$

that coincide on

G

. It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem

Sefe

).

In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given

Sefe

instance, producing a set of equivalent

Sefe

instances without such substructures. The structures we can remove are (1) cutvertices of the

union graph

$G^{\mbox{\textcircled{1}}} \cup G^{\mbox{\textcircled{2}}}$

, (2) cutvertices that are simultaneously a cutvertex in

$G^{\mbox{\textcircled{1}}}$

and

$G^{\mbox{\textcircled{2}}}$

and that have degree at most 3 in

G

, and (3) connected components of

G

that are biconnected but not a cycle.

Second, we give an

O

(

n

2

)-time algorithm for

Sefe

where, for each pole

u

of a P-node

μ

(of a block) of the input graphs, at most three virtual edges of

μ

contain common edges incident to

u

. All algorithms extend to the sunflower case.

Thomas Bläsius, Annette Karrer, Ignaz Rutter

Practical Graph Drawing

Sketched Graph Drawing: A Lesson in Empirical Studies

This paper reports on a series of three similar graph drawing empirical studies, and describes the results of investigating subtle variations on the experimental method. Its purpose is two-fold: to report the results of the experiments, as well as to illustrate how easy it is to inadvertently make conclusions that may not stand up to scrutiny. While the results of the initial experiment were validated, instances of speculative conclusions and inherent bias were identified. This research highlights the importance of stating the limitations of any experiment, being clear about conclusions that are speculative, and not assuming that (even minor) experimental decisions will not affect the results.

Helen C. Purchase

Many-to-One Boundary Labeling with Backbones

In this paper we study

many-to-one boundary labeling with backbone leaders

. In this model, a horizontal backbone reaches out of each label into the feature-enclosing rectangle. Feature points associated with this label are linked via vertical line segments to the backbone. We present algorithms for label number and leader-length minimization. If crossings are allowed, we aim to minimize their number. This can be achieved efficiently in the case of fixed label order. We show that the corresponding problem in the case of flexible label order is NP-hard.

Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, Antonios Symvonis

Streamed Graph Drawing and the File Maintenance Problem

In

streamed graph drawing

, a planar graph,

G

, is given incrementally as a data stream and a straight-line drawing of

G

must be updated after each new edge is released. To preserve the mental map, changes to the drawing should be minimized after each update, and Binucci

et al.

show that exponential area is necessary for a number of streamed graph drawings for trees if edges are not allowed to move at all. We show that a number of streamed graph drawings can, in fact, be done with polynomial area, including planar streamed graph drawings of trees, tree-maps, and outerplanar graphs, if we allow for a small number of coordinate movements after each update. Our algorithms involve an interesting connection to a classic algorithmic problem—the

file maintenance problem

—and we also give new algorithms for this problem in a framework where bulk memory moves are allowed.

Michael T. Goodrich, Paweł Pszona

COAST: A Convex Optimization Approach to Stress-Based Embedding

Visualizing graphs using virtual physical models is probably the most heavily used technique for drawing graphs in practice. There are many algorithms that are efficient and produce high-quality layouts. If one requires that the layout also respect a given set of non-uniform edge lengths, however, force-based approaches become problematic while energy-based layouts become intractable. In this paper, we propose a reformulation of the stress function into a two-part convex objective function to which we can apply semi-definite programming (SDP). We avoid the high computational cost associated with SDP by a novel, compact re-parameterization of the objective function using the eigenvectors of the graph Laplacian. This sparse representation makes our approach scalable. We provide experimental results to show that this method scales well and produces reasonable layouts while dealing with the edge length constraints.

Emden R. Gansner, Yifan Hu, Shankar Krishnan

Subgraphs

Colored Spanning Graphs for Set Visualization

We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A

red-blue-purple spanning graph

(RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected.

We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem is NP-hard. Hence we give an

$(\frac 12\rho+1)$

-approximation, where

ρ

is the Steiner ratio. We also present efficient exact solutions if the points are located on a line or a circle. Finally we consider extensions to more than two sets.

Ferran Hurtado, Matias Korman, Marc van Kreveld, Maarten Löffler, Vera Sacristán, Rodrigo I. Silveira, Bettina Speckmann

Drawing Non-Planar Graphs with Crossing-Free Subgraphs

We initiate the study of the following problem:

Given a non-planar graph G and a planar subgraph S of G, does there exist a straight-line drawing

Γ

of G in the plane such that the edges of S are not crossed in

Γ

?

We give positive and negative results for different kinds of spanning subgraphs

S

of

G

. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of

G

 ∖ 

S

; in this setting different trade-offs between number of bends and drawing area are given.

Patrizio Angelini, Carla Binucci, Giordano Da Lozzo, Walter Didimo, Luca Grilli, Fabrizio Montecchiani, Maurizio Patrignani, Ioannis G. Tollis

Exploring Complex Drawings via Edge Stratification

We propose an approach that allows a user to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on

stratifying

the drawing into

layers

with desired properties; layers can be explored and combined by the user to gradually acquire details. We present stratification heuristics, a user study, and an experimental analysis that evaluates how our stratification heuristics behave on the drawings computed by a variety of popular force-directed algorithms.

Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, Ioannis G. Tollis

Drawing Planar Graphs with a Prescribed Inner Face

Given a plane graph

G

(i.e., a planar graph with a fixed planar embedding) and a simple cycle

C

in

G

whose vertices are mapped to a convex polygon, we consider the question whether this drawing can be extended to a planar straight-line drawing of

G

. We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, it can be computed in the same running time.

Tamara Mchedlidze, Martin Nöllenburg, Ignaz Rutter

Crossings

Metro-Line Crossing Minimization: Hardness, Approximations, and Tractable Cases

Crossing minimization is one of the central problems in graph drawing. Recently, there has been an increased interest in the problem of minimizing crossings between paths in drawings of graphs. This is the

metro-line crossing minimization

problem (MLCM): Given an embedded graph and a set

L

of simple paths, called

lines

, order the lines on each edge so that the total number of crossings is minimized. So far, the complexity of MLCM has been an open problem. In contrast, the problem variant in which line ends must be placed in outermost position on their edges (MLCM-P) is known to be NP-hard.

Our main results answer two open questions: (i) We show that MLCM is NP-hard. (ii) We give an

$O(\sqrt{\log |L|})$

-approximation algorithm for MLCM-P.

Martin Fink, Sergey Pupyrev

Fixed Parameter Tractability of Crossing Minimization of Almost-Trees

We investigate exact crossing minimization for graphs that differ from trees by a small number of additional edges, for several variants of the crossing minimization problem. In particular, we provide fixed parameter tractable algorithms for the 1-page book crossing number, the 2-page book crossing number, and the minimum number of crossed edges in 1-page and 2-page book drawings.

Michael J. Bannister, David Eppstein, Joseph A. Simons

Strict Confluent Drawing

We define

strict confluent drawing

, a form of confluent drawing in which the existence of an edge is indicated by the presence of a smooth path through a system of arcs and junctions (without crossings), and in which such a path, if it exists, must be unique. We prove that it is NP-complete to determine whether a given graph has a strict confluent drawing but polynomial to determine whether it has an

outerplanar

strict confluent drawing with a fixed vertex ordering (a drawing within a disk, with the vertices placed in a given order on the boundary).

David Eppstein, Danny Holten, Maarten Löffler, Martin Nöllenburg, Bettina Speckmann, Kevin Verbeek

Geometric Graphs and Geographic Networks

A Ramsey-Type Result for Geometric ℓ-Hypergraphs

Let

n

 ≥ ℓ ≥ 2 and

q

 ≥ 2. We consider the minimum

N

such that whenever we have

N

points in the plane in general position and the ℓ-subsets of these points are colored with

q

colors, there is a subset

S

of

n

points all of whose ℓ-subsets have the same color and furthermore

S

is in convex position. This combines two classical areas of intense study over the last 75 years: the Ramsey problem for hypergraphs and the Erdős-Szekeres theorem on convex configurations in the plane. For the special case ℓ = 2, we establish a single exponential bound on the minimum

N

such that every complete

N

-vertex geometric graph whose edges are colored with

q

colors, yields a monochromatic convex geometric graph on

n

vertices.

For fixed ℓ ≥ 2 and

q

 ≥ 4, our results determine the correct exponential tower growth rate for

N

as a function of

n

, similar to the usual hypergraph Ramsey problem, even though we require our monochromatic set to be in convex position. Our results also apply to the case of ℓ = 3 and

q

 = 2 by using a geometric variation of the Stepping-up lemma of Erdős and Hajnal. This is in contrast to the fact that the upper and lower bounds for the usual 3-uniform hypergraph Ramsey problem for two colors differ by one exponential in the tower.

Dhruv Mubayi, Andrew Suk

Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations

We consider the problem of finding a planar embedding of a graph at fixed vertex locations that minimizes the total edge length. The problem is known to be NP-hard. We give polynomial time algorithms achieving an

$O(\sqrt{n} \log n)$

approximation for paths and matchings, and an

O

(

n

) approximation for general graphs.

Timothy M. Chan, Hella-Franziska Hoffmann, Stephen Kiazyk, Anna Lubiw

Stub Bundling and Confluent Spirals for Geographic Networks

Edge bundling is a technique to reduce clutter by routing parts of several edges along a shared path. In particular, it is used for visualization of geographic networks where vertices have fixed coordinates. Two main drawbacks of the common approach of bundling the interior of edges are that (i) tangents at endpoints deviate from the line connecting the two endpoints in an uncontrolled way and (ii) there is ambiguity as to which pairs of vertices are actually connected. Both severely reduce the interpretability of geographic network visualizations.

We therefore propose methods that bundle edges at their ends rather than their interior. This way, tangents at vertices point in the general direction of all neighbors of edges in the bundle, and ambiguity is avoided altogether. For undirected graphs our approach yields curves with no more than one turning point. For directed graphs we introduce a new drawing style, confluent spiral drawings, in which the direction of edges can be inferred from monotonically increasing curvature along each spiral segment.

Arlind Nocaj, Ulrik Brandes

Angular Restrictions

On Orthogonally Convex Drawings of Plane Graphs

(Extended Abstract)

We investigate the bend minimization problem with respect to a new drawing style called

orthogonally convex drawing

, which is orthogonal drawing with an additional requirement that each inner face is drawn as an

orthogonally convex polygon

. For the class of bi-connected plane graphs of maximum degree 3, we give a necessary and sufficient condition for the existence of a no-bend orthogonally convex drawing, which in turn, enables a linear time algorithm to check and construct such a drawing if one exists. We also develop a flow network formulation for bend-minimization in orthogonally convex drawings, yielding a polynomial time solution for the problem. An interesting application of our orthogonally convex drawing is to characterize internally triangulated plane graphs that admit floorplans using only orthogonally convex modules subject to certain boundary constraints.

Yi-Jun Chang, Hsu-Chun Yen

Planar and Plane Slope Number of Partial 2-Trees

We prove tight bounds (up to a small multiplicative or additive constant) for the plane and the planar slope numbers of partial 2-trees of bounded degree. As a byproduct of our techniques, we answer a long standing question by Garg and Tamassia about the angular resolution of the planar straight-line drawings of series-parallel graphs of bounded degree.

William Lenhart, Giuseppe Liotta, Debajyoti Mondal, Rahnuma Islam Nishat

Slanted Orthogonal Drawings

We introduce a new model that we call

slanted orthogonal graph drawing

. While in traditional orthogonal drawings each edge is made of axis-aligned line-segments, in slanted orthogonal drawings intermediate diagonal segments on the edges are also permitted, which allows for: (a) smoothening the bends of the produced drawing (as they are replaced by pairs of “half-bends”), and, (b) emphasizing the crossings of the drawing (as they always appear at the intersection of two diagonal segments). We present an approach to compute bend-optimal slanted orthogonal representations, an efficient heuristic to compute close-to-optimal drawings in terms of the total number of bends using quadratic area, and a corresponding LP formulation, when insisting on bend optimality. On the negative side, we show that bend-optimal slanted orthogonal drawings may require exponential area.

Michael A. Bekos, Michael Kaufmann, Robert Krug, Stefan Näher, Vincenzo Roselli

Grids

Drawing Arrangement Graphs in Small Grids, or How to Play Planarity

We describe a linear-time algorithm that finds a planar drawing of every graph of a simple line or pseudoline arrangement within a grid of area

O

(

n

7/6

). No known input causes our algorithm to use area Ω(

n

1 + 

ε

) for any

ε

 > 0; finding such an input would represent significant progress on the famous

k

-set problem from discrete geometry. Drawing line arrangement graphs is the main task in the

Planarity

puzzle.

David Eppstein

Incremental Grid-Like Layout Using Soft and Hard Constraints

We explore various techniques to incorporate grid-like layout conventions into a force-directed, constraint-based graph layout framework. In doing so we are able to provide high-quality layout—with predominantly axis-aligned edges—that is more flexible than previous grid-like layout methods and which can capture layout conventions in notations such as SBGN (Systems Biology Graphical Notation). Furthermore, the layout is easily able to respect user-defined constraints and adapt to interaction in online systems and diagram editors such as Dunnart.

Steve Kieffer, Tim Dwyer, Kim Marriott, Michael Wybrow

Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings

We present a simple and versatile formulation of grid-based graph representation problems as an integer linear program (ILP) and a corresponding SAT instance. In a grid-based representation vertices and edges correspond to axis-parallel boxes on an underlying integer grid; boxes can be further constrained in their shapes and interactions by additional problem-specific constraints. We describe a general

d

-dimensional model for grid representation problems. This model can be used to solve a variety of NP-hard graph problems, including pathwidth, bandwidth, optimum

st

-orientation, area-minimal (bar-

k

) visibility representation, boxicity-

k

graphs and others. We implemented SAT-models for all of the above problems and evaluated them on the Rome graphs collection. The experiments show that our model successfully solves NP-hard problems within few minutes on small to medium-size Rome graphs.

Therese Biedl, Thomas Bläsius, Benjamin Niedermann, Martin Nöllenburg, Roman Prutkin, Ignaz Rutter

Curves and Routes

Untangling Two Systems of Noncrossing Curves

We consider two systems (

α

1

,…,

α

m

) and (

β

1

,…,

β

n

) of curves drawn on a compact two-dimensional surface

$\mathcal{M}$

with boundary. Each

α

i

and each

β

j

is either an arc meeting the boundary of

$\mathcal{M}$

at its two endpoints, or a closed curve. The

α

i

are pairwise disjoint except for possibly sharing endpoints, and similarly for the

β

j

. We want to “untangle” the

β

j

from the

α

i

by a self-homeomorphism of

$\mathcal{M}$

; more precisely, we seek an homeomorphism

$\varphi\:\mathcal{M}\to\mathcal{M}$

fixing the boundary of

$\mathcal{M}$

pointwise such that the total number of crossings of the

α

i

with the

ϕ

(

β

j

) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds.

We prove that if

$\mathcal{M}$

is planar, i.e., a sphere with

h

 ≥ 0 boundary components (“holes”), then

O

(

mn

) crossings can be achieved (independently of

h

), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface

$\mathcal{M}$

with

h

holes and of (orientable or nonorientable) genus

g

 ≥ 0, we obtain an

O

((

m

 + 

n

)

4

) upper bound, again independent of

h

and

g

.

Jiří Matoušek, Eric Sedgwick, Martin Tancer, Uli Wagner

Drawing Permutations with Few Corners

A permutation may be represented by a collection of paths in the plane. We consider a natural class of such representations, which we call tangles, in which the paths consist of straight segments at 45 degree angles, and the permutation is decomposed into nearest-neighbour transpositions. We address the problem of minimizing the number of crossings together with the number of corners of the paths, focusing on classes of permutations in which both can be minimized simultaneously. We give algorithms for computing such tangles for several classes of permutations.

Sergey Bereg, Alexander E. Holroyd, Lev Nachmanson, Sergey Pupyrev

Dynamic Traceroute Visualization at Multiple Abstraction Levels

We present a system, called

TPlay

, for the visualization of the traceroutes performed by the Internet probes deployed by active measurement projects. These traceroutes are continuously executed towards selected Internet targets.

TPlay

allows to look at traceroutes at different abstraction levels and to animate the evolution of traceroutes during a selected time interval. The system has been extensively tested on traceroutes performed by RIPE Atlas [22] Internet probes.

Massimo Candela, Marco Di Bartolomeo, Giuseppe Di Battista, Claudio Squarcella

Graph Drawing Contest

Graph Drawing Contest Report

This report describes the 20th Annual Graph Drawing Contest, held in conjunction with the 2013 Graph Drawing Symposium in Bordeaux (Talence), France. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology.

Christian A. Duncan, Carsten Gutwenger, Lev Nachmanson, Georg Sander

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise