Accepted papers

Listed in no particular order. Clicking the “[+]” after the title will show the abstract for that paper.

• Monotone crossing number [+]
  Janos Pach and Geza Toth

  The monotone crossing number of G is defined as the smallest number of crossing points in a drawing of G in the plane, where every edge is represented by an x-monotone curve, that is, by a connected continuous arc with the property that every vertical line intersects it in at most one point. It is shown that this parameter can be strictly larger than the classical crossing number cr(G), but it is bounded from above by twice the square of cr(G). This is in sharp contrast with the behavior of the rectilinear crossing number, which cannot be bounded from above by any function of cr(G).

• On Point-sets that Support Planar Graphs [+]
  Vida Dujmovic, Will Evans, Sylvain Lazard, William Lenhart, Giuseppe Liotta, David Rappaport and Steve Wismath

  A universal point-set supports a crossing-free drawing of any planar graph. If bends on edges of the drawing are permitted, universal point-sets of size $n$ are known, but only if the bend-points are in arbitrary positions. If the locations of the bend-points must also be supplied, we prove that any planar graph with $n$ vertices can be drawn on a universal set S of $O(n^2/\log n)$ points with at most one bend per edge and with the vertices and the bend points in S. If two bends per edge are allowed, we show that $O(n\log n)$ points are  sufficient, and if three bends per edge are allowed, $\Theta(n)$ points are sufficient. When no bends on edges are permitted, no universal point-set of size $o(n^2)$ is known for the class of planar graphs. We show that a set of points in balanced biconvex position supports the class of maximum degree 3 series-parallel lattices.

• On the Page Number of Upward Planar Directed Acyclic Graphs [+]
  Fabrizio Frati, Radoslav Fulek and Andres Ruiz-Vargas

  In this paper we study the page number of upward planar directed acyclic graphs. We prove that the page number of any upward planar directed acyclic graph G is a function of the page number of a four-connected subgraph of G; further, we provide an upper bound on the page number of G if G has small diameter; finally, we show that every upward planar directed acyclic graph has small page number if and only if every upward planar directed acyclic graph with small degree does.

• Confluent Hasse diagrams [+]
  David Eppstein and Joseph A. Simons

  We show that a transitively reduced digraph has a confluent upward drawing if and only if its reachability relation has order dimension at most two. In this case, we construct a confluent upward drawing with O(n^2) features, in an O(n) x O(n) grid in O(n^2) time. For the digraphs representing series-parallel partial orders we show how to construct a drawing with O(n) features in an O(n) x O(n) grid in O(n) time from a series-parallel decomposition of the partial order. Our drawings are optimal in the number of confluent junctions they use.

• Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings [+]
  Michael J. Bannister and David Eppstein

  We show that several problems of compacting orthogonal graph drawings to use the minimum number of rows or the minimum possible area cannot be approximated to within better than a polynomial factor in polynomial time unless P=NP. However, there is a fixed-parameter-tractable algorithm for testing whether a drawing can be compacted to a given number of rows.

• Right Angle Crossing Graphs and 1-planarity [+]
  Peter Eades and Giuseppe Liotta

  A Right Angle Crossing Graph (also called RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A $1$-planar graph is a graph that has a drawing where every edge is crossed at most once. We study the relationship between RAC graphs and $1$-planar graphs in the extremal case that the RAC graphs have as many edges as possible. It is known that a maximally dense RAC graph with $n > 3$ vertices has $4n-10$ edges. We show that every maximally dense RAC graph is $1$-planar. Also, we show that for every integer $i$ such that $i \geq 0$, there exists a $1$-planar graph with $n=8 + 4i$ vertices and $4n - 10$ edges that is not a RAC graph.

• Upward Planarity Testing of Embedded Mixed Graphs [+]
  Carla Binucci and Walter Didimo

  A mixed graph has both directed and undirected edges. We study an upward planarity testing problem for embedded mixed graphs and solve it using Integer Linear Programming. Experiments show the efficiency of our technique.

• $k$-quasi planar graphs [+]
  Andrew Suk

  A topological graph is \emph{$k$-quasi-planar} if it does not contain $k$ pairwise crossing edges.  A topological graph is \emph{simple} if every pair of its edges intersect at most once (either at a vertex or at their intersection).  In 1996, Pach, Shahrokhi, and Szegedy \cite{pach} showed that every $n$-vertex simple $k$-quasi-planar graph contains at most $O\left(n(\log n)^{2k-4}\right)$ edges.  This upper bound was recently improved (for large $k$) by Fox and Pach \cite{fox} to $n(\log n)^{O(\log k)}$.  In this note, we show that all such graphs contain at most $(n\log^2n )2^{\alpha^{c_k}(n)}$ edges, where $\alpha(n)$ denotes the inverse Ackermann function and $c_k$ is a constant that depends only on $k$.

• Proportional Contact Representations of Planar Graphs [+]
  Muhammad Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann and Stephen G. Kobourov

  We study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by a point-contact or a side-contact between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Several natural optimization goals for such representations include minimizing the complexity of the polygons, the cartographic error, and the unused area. We describe constructive algorithms for proportional contact representations with optimal complexity for general planar graphs and planar 2-segment graphs, which include maximal outerplanar graphs and partial 2-trees.

• Edge Routing with Ordered Bundles [+]
  Sergey Pupyrev, Lev Nachmanson, Sergey Bereg and Alexander E. Holroyd

  We propose a new approach to edge bundling. The approach starts by routing the edge paths to minimize a weighted sum of the total length of the paths together with the ink required to draw them. As this problem is NP-hard, we provide an efficient heuristic that finds an approximate solution. Our approach continues by separating edges belonging to the same bundle. To achieve this, we provide a new and efficient algorithm that solves a variant of the metro-line crossing minimization problem. The method creates aesthetically pleasing edge routes that give an overview of the global graph structure, while still drawing each edge separately, without intersecting graph nodes, and with few crossings.

• Orthogeodesic Point-Set Embedding of Trees [+]
  Emilio Di Giacomo, Fabrizio Frati, Radoslav Fulek, Luca Grilli and Marcus Krug

  Let S be a set of N points in the plane, and let G a graph with n vertices (n <= N). An orthogeodesic point-set embedding of G on S is a drawing of G such that each vertex is drawn as a point of S and each edge is a chain of horizontal and vertical segments whose length is equal to the Manhattan distance of its end vertices.

  We study the following problem. Given a family of trees F what is the minimum value f(n) such that every n-vertex tree in F admits an orthogeodesic point-set embedding on every point set of size f(n)? We consider both planar and non-planar orthogeodesic point-set embeddings; also, we consider the case when edges can be arbitrary orthogeodesic chains and the case when edges are required to be L-shaped chains. We provide polynomial upper bounds on f(n) for all the considered variants of the problem.

• Accelerated Bend Minimization [+]
  Sabine Cornelsen and Andreas Karrenbauer

  We present an $O( n^{3/2})$ algorithm for minimizing the number of bends in an orthogonal drawing of a plane graph. It has been posed as a long standing open problem at \emph{Graph Drawing 2003}, whether the bound of $O(n^{7/4}\sqrt{\log n})$ shown by Garg and Tamassia in 1996 could be improved. To answer this question, we show how to solve the uncapacitated min-cost flow problem on a planar bidirected graph with bounded costs and face sizes in $O(n^{3/2})$ time.

• Embedding Plane $3$-Trees in $\mathbb{R}^2$ and $\mathbb{R}^3$ [+]
  Stephane Durocher, Debajyoti Mondal, Rahnuma Islam Nishat, Md. Saidur Rahman and Sue Whitesides

  A point-set embedding of a planar graph $G$ with $n$ vertices on a set $P$ of $n$ points in $\mathbb{R}^d$, $d\ge 1$, is a straight-line drawing of $G$, where the vertices of $G$ are mapped to distinct points of $P$. The problem of computing a point-set embedding of $G$ on $P$ is NP-complete in $\mathbb{R}^2$, even when $G$ is $2$-outerplanar and the points are in general position. On the other hand, if the points of $P$ are in general position in $\mathbb{R}^3$, then any bijective mapping of the vertices of $G$ to the points of $P$ determines a point-set embedding of $G$ on $P$. In this paper we give an $O(n^{4/3+\epsilon} \log^2n)$-expected time algorithm to decide whether a plane $3$-tree with $n$ vertices admits a point-set embedding on a given set of $n$ points in general position in $\mathbb{R}^2$ and compute such an embedding if it exists, for any fixed $\epsilon{>}0$. We extend our algorithm to embed a subclass of $4$-trees on a point set in $\mathbb{R}^3$ in the form of nested tetrahedra. We also prove that given a plane $3$-tree $G$ with $n$ vertices, a set $P$ of $n$ points in $\mathbb{R}^3$  that are not necessarily in general position and a mapping of the three outer vertices of $G$ to three different points of $P$, it is NP-complete to decide if $G$  admits a point-set embedding on $P$  respecting the given mapping of the outer vertices.

• Planar Open Rectangle-of-Influence Drawings with Non-Aligned Frames [+]
  Soroush Alamdari and Therese Biedl

  A straight line drawing of a graph is an open weak rectangle-of-influence (RI) drawing, if there is no vertex in the relative interior of the axis parallel rectangle induced by the end points of each edge. No algorithm is known to test whether a graph has a planar open weak RI-drawing, not even for inner triangulated graphs.

  In this paper, we study RI-drawings that must have a non-aligned frame, i.e., the graph obtained from removing the interior of every filled triangle is drawn such that no two vertices have the same coordinate. We give give a polynomialalgorithm to test whether an inner triangulated graph has an open weak RI-drawing with non-aligned frame.

• Triangulations with circular arcs [+]
  Franz Aurenhammer, Oswin Aichholzer, Wolfgang Aigner, Bert Juettler, Guenter Rote and Katerina Cech Dobiasova

  An important objective in the choice of a triangulation of a given point set is that the smallest angle becomes as large as possible. In the straight line case, it is known that the Delaunay triangulation is optimal in this respect. We propose and study the concept of a circular arc triangulation, a simple and effective alternative that offers flexibility for additionally enlarging small angles. We show that angle optimization and related questions lead to linear programming problems that can be formulated as simple graph-theoretic problems, and we define flipping operations in arc triangles. Moreover, special classes of arc triangulations are considered, for applications in graph drawing and finite element methods.

• Monotone Drawings of Graphs with Fixed Embedding [+]
  Patrizio Angelini, Walter Didimo, Stephen Kobourov, Tamara Mchedlidze, Vincenzo Roselli, Antonios Symvonis and Stephen Wismath

  A drawing of a graph is a \emph{monotone drawing} if for every pair of vertices $u$ and $v$, there is a path drawn from $u$ to $v$ that is monotone in some direction. In this paper we investigate planar monotone drawings in the \emph{fixed embedding setting}, i.e., a planar embedding of the graph is given as part of the input that must be preserved by the drawing algorithm. In this setting we prove that every planar graph on $n$ vertices admits a planar monotone drawing with at most two bends per edge and with at most $4n-10$ bends in total; such a drawing can be computed in linear time and in polynomial area. We also show that two bends per edge are sometimes necessary on a linear number of edges of the graph. Furthermore, we investigate subclasses of planar graphs that can be realized as embedding-preserving monotone drawings with straight-line edges, and we show that biconnected embedded planar graphs and outerplane graphs always admit such drawings, which can be computed in linear time.

• How to Visualize the K-Root Name Server (Demo) [+]
  Giuseppe Di Battista, Claudio Squarcella and Wolfgang Nagele

  We present a system that visualizes the evolution of the service provided by one of the most popular root name servers, called K, operated by the RIPE Network Coordination Centre (RIPE NCC) and distributed in several locations (instances) worldwide. The system can be used either to monitor what happened during a prescribed time interval or to observe the status of the service in near real-time. The system visualizes how and when the clients of K migrate from one instance to another, how the number of clients associated with each instance changes over time, and what are the instances that contribute to offer the service to a selected Internet Service Provider. In addition, the visualization aims at distinguishing usual from unusual operational patterns. This helps not only to improve the quality of the service but also to spot security-related issues and to investigate unexpected routing changes.

• TGI-EB: A New Framework for Edge Bundling integrating Topology, Geometry and Importance [+]
  Quan Nguyen, Seok-Hee Hong and Peter Eades

  Recently, edge bundling methods became popular for visualising large dense networks, however, most of previous work mainly relies on geometry to define spatial compatibility between the edges. In this paper, we present a new framework for edge bundling, which tightly integrates topology, geometry and importance. In particular, we introduce new edge compatibility measures, called importance compatibility and topology compatibility. More specifically, we present four variations of force directed edge bundling method, based on the framework: Centrality-based bundling, Radial bundling, Topology-based bundling, and Orthogonal bundling. Our experimental results with social networks, biological networks, geographic networks and clustered graphs indicate that our new framework can be very useful to highlight the most important topological skeletal structures of the input network. For example, our Radial bundling has proved very useful to highlight significant functional groups in biological networks. In fact, our visualisation guided biologists to derive new biological hypothesis, and currently laboratory experiments are being conducted.

• Advances in the Planarization Method: Effective Multiple Edge Insertions [+]
  Markus Chimani and Carsten Gutwenger

  The planarization method is the strongest known method to heuristically find good solutions to the general crossing number problem in graphs: starting from a planar subgraph, one iteratively inserts edges, representing crossings via dummy nodes. In the recent years, several improvements both from the practical and the theoretical point of view have been made. We review these advances and conduct an extensive study of the algorithms' practical implications. Thereby, we present the first implementation of an approximation algorithm for the crossing number problem of general graphs, and compare the obtained results with known exact crossing number solutions.

• Approximate Proximity Drawings [+]
  William Evans, Emden Gansner, Michael Kaufmann, Giuseppe Liotta, Henk Meijer and Andreas Spillner

  We introduce and study a generalization of the well-known region of influence proximity drawings, called \emph{($\varepsilon_1,\varepsilon_2)$-proximity drawings}. Intuitively,  given a definition of proximity and two real numbers $\varepsilon_1 \geq 0$ and $\varepsilon_2 \geq 0$, an $(\varepsilon_1,\varepsilon_2)$-proximity drawing of a graph is a planar straight-line drawing $\Gamma$ such that: (i) for every pair of adjacent vertices $u,v$, their proximity region ``shrunk'' by the multiplicative factor $\frac{1}{1+\varepsilon_1}$ does not contain any vertices of $\Gamma$; (ii) for every pair  of non-adjacent vertices $u,v$,  their proximity region ``blown-up'' by the factor $(1+\varepsilon_2)$ contains some vertices of $\Gamma$ other than $u$ and $v$. We show that by using this generalization, we can significantly enlarge the family of the representable planar graphs for relevant definitions of proximity drawings, including Gabriel drawings, Delaunay drawings, and $\beta$-drawings, even for arbitrarily small values of $\varepsilon_1$ and $\varepsilon_2$. We also study the extremal case of ($0,\varepsilon_2)$-proximity drawings, which generalize the well-known weak proximity drawing paradigm.

• Every graph admits an unambiguous bold drawing [+]
  Janos Pach

  Let r and w be fixed positive numbers, w < r. In a bold drawing of a graph, every vertex is represented by a disk of radius r, and every edge by a narrow rectangle of width w. We solve a problem of van Kreveld by showing that every graph admits a bold drawing in which the region occupied by the union of the disks and rectangles representing the vertices and edges does not contain any disk of radius r other than the ones representing the vertices.

• Generalizing Geometric Graphs [+]
  Edith Brunel, Andreas Gemsa, Marcus Krug, Ignaz Rutter and Dorothea Wagner

  Network visualization is essential for understanding the data obtained from huge real-world networks such as flight-networks, the AS-network or social networks. Although we can compute layouts for these networks reasonably fast, even the most recent display media are not capable of displaying these layouts in an adequate way. Moreover, the human viewer may be overwhelmed by the displayed level of detail. The increasing amount of data therefore requires techniques aiming at a sensible reduction of the visual complexity of huge layouts.

  We consider the problem of computing a generalization of a given layout reducing the complexity of the drawing to an amount that can be displayed without clutter and handled by a human viewer. We take a first step at formulating graph generalization  within a mathematical model and we consider the resulting problems from an algorithmic point of view. Although these problems turn out to be NP-hard in general, we provide efficient approximation algorithms as well as efficient and effective heuristics. At the end of the paper we showcase some sample generalizations.

• Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane [+]
  Rik Sarkar

  This paper considers the problem of embedding trees into the hyperbolic plane. We show that any tree can be realized as the Delaunay graph of its embedded vertices. Particularly, a weighted tree can be embedded  such that the weight on each edge is realized as the hyperbolic distance between its embedded vertices. Thus the embedding preserves the metric information of the tree along with its topology. Further, the distance distortion between non adjacent vertices can be made arbitrarily small -- less than a $(1+\eps)$ factor for any given $\eps$. Existing results on low distortion of embedding discrete metrics into trees carry over to hyperbolic metric through this result. The Delaunay character implies useful properties such as guaranteed greedy routing and realization as minimum spanning trees.

• Upward Point Set Embeddability for Convex Point Sets is in P [+]
  Michael Kaufmann, Tamara Mchedlidze and Antonios Symvonis

  In this paper, we present a polynomial dynamic programming algorithm which tests whether an $n$-vertex directed tree $T$ has an upward planar embedding into a convex point-set $S$ of size $n$. Further, we extend our approach to the class of outerplanar digraphs. This nontrivial and surprising result implies that any given digraph can be efficiently tested for an upward planar embedding into a given convex point set.

• Adjacent Crossings Do Matter [+]
  Radoslav Fulek, Michael Pelsmajer, Marcus Schaefer and Daniel Stefankovic

  In a drawing of a graph, two edges form an odd pair if they cross each other an odd number of times.  A pair of edges is independent if they share no endpoint. For a graph G, let ocr(G) be the smallest number odd pairs in a drawing of G and let iocr(G) be the smallest number of independent odd pairs in a drawing of G. We construct a graph G with iocr(G)<ocr(G), answering a question that was referred to in several papers.

  The graph G was found via considering monotone graph drawings of ordered graphs. A drawing of a graph is x-monotone if every edge intersects every vertical line at most once and every vertical line contains at most one vertex.  A graph is ordered if each of its vertices is assigned a distinct x-coordinate.  We construct a family of ordered graphs such that for x-monotone drawings, the monotone variants of ocr and iocr satisfy mon-iocr(G)< O( monmocr(G)^(1/2) ).

• Visual Community Detection: an Evaluation of 2D, 3D Perspective and 3D Stereoscopic displays [+]
  Nicolas Greffard, Fabien Picarougne and Pascale Kuntz

  3D drawing problems of the 90s were essentially restricted on representations in 3D perspective. However, recent technologies offer 3D stereoscopic representations of high quality which allow the introduction of binocular disparities, which is one of the main depth perception cues, not provided by the 3D perspective. This paper explores the relevance of stereoscopy for the visual identification of communities, which is a task of great importance in the analysis of social networks. A user study conducted on 35 participants with graphs of various complexity shows that stereoscopy outperforms 3D perspective in the vast majority of the cases. When comparing stereoscopy with 2D layouts, the response time is significantly lower for 2D but the quality of the results closely depend on the graph complexity : for a large number of clusters and a high probability of cluster overlapping stereoscopy outperforms 2D whereas for simple structures 2D layouts are more efficient.

• Classification of Planar Upward Embedding [+]
  Christopher Auer, Christian Bachmaier, Franz Josef Brandenburg and Andreas Gleißner

  We consider plane upward drawings of directed graphs on arbitrary surfaces where the upward direction is defined by a vector field.  This generalizes earlier approaches using surfaces with a fixed embedding in R^3 and introduces new classes of planar upward drawable graphs, where some of them even allow cycles. Our approach leads to a classification of planar upward embeddability.

  In particular, we show the coincidence of the classes of planar upward drawable graphs on the sphere and on the (standing) cylinder with a fixed embedding in R^3. These classes coincide with our classes of planar upward drawable graphs with a homogeneous field on a cylinder and with a radial field on the plane.

  A cyclic field on the plane introduces the new class RUP of upward drawable graphs, which can be embedded on a rolling cylinder. We establish strict inclusions for planar upward drawability on the plane, the sphere, the rolling cylinder, and the torus, even for acyclic graphs. Finally, upward drawability remains NP-hard for the (standing) cylinder and the torus; for the cylinder this was left as an open problem by Limaye et al.

• Evaluating Partially Drawn Links for Directed Graph Edges [+]
  Michael Burch, Natalia Konevtsova, Corinna Vehlow and Daniel Weiskopf

  In this paper we investigate the readability of node-link diagrams for directed graphs when using partially drawn links instead of showing each link explicitly in its full length. Providing the complete link information between related nodes in a graph can lead to visual clutter caused by many edge crossings. We chose the force-directed layout proposed by Fruchterman and Reingold~\cite{Fruchterman:91} to represent the graphs. Visual clutter is further reduced by drawing only partial links and we ask the question if such graph diagrams are still readable, understandable, and interpretable. We conducted a controlled user experiment with 40 participants to uncover differences in accuracies and completion times for three different tasks: Existence of a direct link, existence of a path with exactly one intermediate node, and detection of the node with the most outgoing edges. Furthermore, we compared tapered and traditional edge representations, three different graph sizes, and six different link lengths. As a major result we obtain that partially drawn links often lead to shorter task completion times but also to higher error rates due to target node ambiguities. This phenomenon occurs for nearly all graph sizes, all tasks, and both tapered and traditional edge representations when using partially drawn links. In some scenarios, task completion time and error rate can also be lower simultaneously.  

• Pinning Balloons with Perfect Angles and Optimal Area [+]
  Immanuel Halupczok and André Schulz

  We study the problem of arranging a set of $n$ disks with prescribed radii on $n$ rays emanating from the origin  such that two neighboring rays are separated by an angle of $2\pi/n$. The center of the disks have to lie on the rays, and no two disk centers are allowed to lie on the same ray. We require that the disks have disjoint interiors, and that for every ray the segment between the origin and the boundary of its associated disk avoids the interior of the disks. Let $R$ be the sum of the disk radii. We introduce a greedy strategy that constructs such a disk arrangement such that all disks can be covered with a disk  centered at the origin whose radius is at most $2R$, which is best possible. The greedy strategy  needs $O(n)$ arithmetic operations.

  As an application of our result we present an algorithm for embedding unordered trees with straight lines such that it can be covered with a disk of radius $n^{3.0367}$, while having no edge of  length smaller than 1. The tree drawing algorithm is an enhancement of  a recent result by Duncan \emph{et al.} [Symp.~of Graph Drawing, 2010] that exploits the heavy-edge tree decomposition technique to construct a drawing of the tree that can be covered by a disk of radius  $2 n^4$.

• Drawing cubic graphs with the four basic slopes [+]
  Padmini Mukkamala and Dömötör Pálvölgyi

  We show that every cubic graph can be drawn in the plane with straight-line edges using only the four basic slopes $\{0,\pi/4,\pi/2,3\pi/4\}$. We also prove that four slopes have this property if and only if we can draw $K_4$ with them.

• Overloaded Orthogonal Drawings [+]
  Evgenios M. Kornaropoulos and Ioannis G. Tollis

  Orthogonal drawings are widely used for graph visualization due to their high clarity of representation. In this paper we present a technique called Overloaded Orthogonal Drawing. In the first phase, vertices are placed on grid points following a relaxed version of dominance drawing, called weak dominance condition. In the second phase we perform edge routing. In order to simplify these drawings we use an overloading technique. All algorithms are simple and easy to implement and can be applied to directed acyclic graphs, planar, non-planar and also undirected graphs. We also present bounds on the number of bends and the area. Overloaded Orthogonal drawings present several interesting properties such as efficient visual edge confirmation as well as simplicity and clarity of the drawing.

• Upper bound constructions for untangling planar geometric graphs [+]
  Javier Cano, Csaba D. Tóth and Jorge Urrutia

  For every $n\in \mathbb{N}$, there is a straight-line drawing $D_n$ of a planar graph on $n$ vertices such that in any {\em crossing-free} straight-line drawing of the graph, at most $O(n^{.4982})$ vertices lie at the same position as in $D_n$. This improves on an earlier bound of $O(\sqrt{n})$ by~Goaoc~{\em et al.}

• Optimizing a radial layout of bipartite graphs for a tool visualizing security alerts [+]
  Maxime Dumas, Michael Mcguffin, Jean-Marc Robert and Marie-Claire Willig

  Efficient tools are crucial to visualize huge quantities of information. While developing these tools, numerous graph drawing problems have to be addressed. We present the solutions that have been used to minimize the cluttering in a radial visualization of a bipartite graph. Such a graph has been used to visualize the alerts generated by an intrusion detection system (IDS) protecting a network. The proposed solutions rely essentially on (i) edge bundling to reduce the number of edges to display and (ii) the minimisation of the total sum of the edge lengths. \keywords{IDS alerts, bipartite graph layout}

• Small Point Sets for Simply-Nested Planar Graphs [+]
  Patrizio Angelini, Giuseppe Di Battista, Michael Kaufmann, Tamara Mchedlidze, Vincenzo Roselli and Claudio Squarcella

  A point set $P \subseteq \mathbb{R}^2$ is universal for class $\cal G$ if every graph of ${\cal G}$ has a planar straight-line embedding into $P$. We prove that there exists a $O(n (\frac{\log n}{\log\log n})^2)$ size universal point set for the class of simply-nested $n$-vertex planar graphs. This is a step towards a full answer for the  well-known open problem on the size of the smallest universal point sets for planar graphs.

• Planar and Poly-Arc Lombardi Drawings [+]
  Christian Duncan, David Eppstein, Michael Goodrich, Stephen G. Kobourov and Maarten Löffler

  In Lombardi drawings of graphs, edges are represented as circular arcs and the edges incident on vertices have perfect angular resolution. However, not every graph has a Lombardi drawing and not every planar graph has a planar Lombardi drawing. We introduce k-Lombardi drawings, in which each edge may be drawn with k circular arcs; we show that every graph has a smooth 2-Lombardi drawing and every planar graph has a smooth planar 3-Lombardi drawing. We also investigate related topics connecting planarity and Lombardi drawings.

• A Quantitative Comparison of Stress-Minimization Approaches for Offline Dynamic Graph Drawing [+]
  Ulrik Brandes and Martin Mader

  In dynamic graph drawing, the input is a sequence of graphs for which a sequence of layouts is to be generated such that the quality of individual layouts is balanced with layout stability over time.  For the important stress-minimization approach to static graph drawing, qualitatively different extensions to the dynamic case have been proposed, but little is known about their relative utility.  We report on a quantitative study comparing the three prototypical variants.  While some findings are more subtle, the linking approach connecting consecutive instances of the same vertex is found to be the overall method of choice.

• Force-Directed Lombardi-Style Graph Drawing [+]
  Roman Chernobelskiy, Kathryn Cunningham, Michael Goodrich, Stephen Kobourov and Lowell Trott

  A Lombardi drawing of a graph is defined as one in which vertices are represented as points, edges are represented as circular arcs between their endpoints, and every vertex has perfect angular resolution (angles between consecutive edges, as measured by the tangents to the circular arcs at the vertex, all have the same degree). We describe two algorithms that create “Lombardi-style” drawings (which we also call near-Lombardi drawings), in which all edges are still circular arcs, but some vertices may not have perfect angular resolution. Both of these algorithms take a force-directed, spring-embedding approach, with one using forces at edge tangents to produce curved edges and the other using dummy vertices on edges for this purpose. As we show, these approaches both produce near-Lombardi drawings, with one being slightly better at achieving near-perfect angular resolution and the other being slightly better at balancing vertex placements.