Graph Drawing and Network Visualization

Algorithms for laying out large graphs have seen significant progress in the past decade. However, browsing large graphs remains a challenge. Rendering thousands of graphical elements at once often results in a cluttered image, and navigating these elements naively can cause disorientation. To address this challenge we propose a method called GraphMaps, mimicking the browsing experience of online geographic maps.GraphMaps creates a sequence of layers, where each layer refines the previous one. During graph browsing, GraphMaps chooses the layer corresponding to the zoom level, and renders only those entities of the layer that intersect the current viewport. The result is that, regardless of the graph size, the number of entities rendered at each view does not exceed a predefined threshold, yet all graph elements can be explored by the standard zoom and pan operations.GraphMaps preprocesses a graph in such a way that during browsing, the geometry of the entities is stable, and the viewer is responsive. Our case studies indicate that GraphMaps is useful in gaining an overview of a large graph, and also in exploring a graph on a finer level of detail.

Graphs provide a visual means for examining relation data and force-directed methods are often used to lay out graphs for viewing. Making sense of a dynamic graph as it evolves over time is challenging, and previous force-directed methods were designed for static graphs. In this paper, we present an incremental version of a multilevel multi-pole layout method with a refinement scheme incorporated, which enables us to visualize online dynamic networks while maintaining a mental map of the graph structure. We demonstrate the effectiveness of our method and compare it to previous methods using several network data sets.

Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. Here we present a novel multilevel algorithm to compute a graph layout with respect to a recently proposed metric that combines layout stress and entropy. As opposed to previous work, we do not solve the linear systems of the maxent-stress metric with a typical numerical solver. Instead we use a simple local iterative scheme within a multilevel approach. To accelerate local optimization, we approximate long-range forces and use shared-memory parallelism. Our experiments validate the high potential of our approach, which is particularly appealing for dynamic graphs. In comparison to the previously best maxent-stress optimizer, which is sequential, our parallel implementation is on average 30 times faster already for static graphs (and still faster if executed on one thread) while producing a comparable solution quality.

In this paper we study the problem of designing a graph drawing algorithm for large graphs. The algorithm must be simple to implement and the computing infrastructure must not require major hardware or software investments. We report about the experimental analysis of a simple implementation of a spring embedder in Giraph, a vertex-centric open source framework for distributed computing. The algorithm is tested on real graphs of up to 1 million edges by using a cheap PaaS (Platform as a Service) infrastructure of Amazon. We can afford drawing graphs with about one million edges in about 8 min, by spending less than 1 USD per drawing for the cloud computing infrastructure.

The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs as they compute a quadratic number of forces in each iteration. We speed up this computation by using an approximation based on the well-separated pair decomposition.We perform experiments on a large number of graphs and show that we can strongly reduce the runtime—even on graphs with less then a hundred vertices—without a significant influence on the quality of the drawings (in terms of number of crossings and deviation in edge lengths).

If a graph embeds in a surface with k crosscaps, does it always have an embedding in the same surface in which every edge passes through each crosscap at most once? This well-known open problem can be restated using crossing numbers: the degenerate crossing number, dcr(G), of G equals the smallest number k so that G has an embedding in a surface with k crosscaps in which every edge passes through each crosscap at most once. The genus crossing number, gcr(G), of G equals the smallest number k so that G has an embedding in a surface with k crosscaps. The question then becomes whether dcr(G) = gcr(G), and it is in this form that it was first asked by Mohar.We show that dcr(G) $$\le $$ 6 gcr(G), and dcr(G) = gcr(G) as long as dcr(G) $$\le $$ 3. We can separate dcr and gcr for (single-vertex) graphs with embedding schemes, but it is not clear whether the separating example can be extended into separations on simple graphs. Finally, we show that if a graph can be embedded in a surface with crosscaps, then it has an embedding in that surface in which every edge passes through each crosscap at most twice. This implies that dcr is $$\mathrm {\mathbf {NP}}$$-complete.

Answering an open question from 2007, we construct infinite k-crossing-critical families of graphs which contain vertices of any prescribed odd degree, for sufficiently large k. From this we derive that, for any set of integers D such that $$\min (D)\ge 3$$ and $$3,4\in D$$, and for all sufficiently large k there exists a k-crossing-critical family such that the numbers in D are precisely the vertex degrees which occur arbitrarily often in any large enough graph in this family. We also investigate what are the possible average degrees of such crossing-critical families.

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth $$O(\sqrt{(g+1)(k+1)n})$$ and layered treewidth $$O((g+1)k)$$, and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth $$O(\sqrt{(k+1)n})$$ and layered treewidth $$O(k+1)$$, which are tight bounds that improve a previously known $$O((k+1)^{3/4}n^{1/2})$$ treewidth bound. Additionally, we show that for $$g<m$$, every m-edge graph can be embedded on a surface of genus g with $$O((m/(g+1))\log ^2 g)$$ crossings per edge, which is tight to a polylogarithmic factor.

A drawing of a graph G is radial if the vertices of G are placed on concentric circles $$C_1, \ldots , C_k$$ with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling.We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.

A drawing of a graph can be understood as an arrangement of geometric objects. In the most natural setting the arrangement is formed by straight-line segments. Every cubic planar 3-connected graph with n vertices has such a drawing with only $$n/2 + 3$$ segments, matching the lower bound. This result is due to Mondal et al. [J. of Comb. Opt., 25], who gave an algorithm for constructing such drawings.We introduce two new algorithms that also produce drawings with $$n/2 + 3$$ segments. One algorithm is based on a sequence of dual edge contractions, the other is based on a recursion of nested cycles. We also show a flaw in the algorithm of Mondal et al. and present a fix for it. We then compare the performance of these three algorithms by measuring angular resolution, edge length and face aspect ratio of the constructed drawings. We observe that the corrected algorithm of Mondal et al. mostly outperforms the other algorithms, especially in terms of angular resolution. However, the new algorithms perform better in terms of edge length and minimal face aspect ratio.

In a book embedding, the vertices of a graph are placed on the spine of a book and the edges are assigned to pages, so that edges of the same page do not cross. In this paper, we approach the problem of determining whether a graph can be embedded in a book of a certain number of pages from a different perspective: We propose a simple and quite intuitive SAT formulation, which is robust enough to solve non-trivial instances of the problem in reasonable time. As a byproduct, we show a lower bound of 4 on the page number of 1-planar graphs.

The approach by Sugiyama et al. is widely used to automatically draw directed graphs. One of its steps is to assign horizontal coordinates to nodes. Brandes and Koepf presented a method that proved to work well in practice. We extend this method to make it possible to draw diagrams with nodes that have considerably different sizes and with edges that have fixed attachment points on a node’s perimeter (ports). Our extensions integrate seamlessly with the original method and preserve the linear execution time.

It is well-known that every graph with maximum degree 4 has an orthogonal drawing with area at most $$\frac{49}{64}n^2+O(n)\approx 0.76n^2$$. In this paper, we show that if the graph is 3-connected, then the area can be reduced even further to $$\frac{9}{16}n^2+O(n) \approx 0.56n^2$$. The drawing uses the 3-canonical order for (not necessarily planar) 3-connected graphs, which is a special Mondshein sequence and can hence be computed in linear time. To our knowledge, this is the first application of a Mondshein sequence in graph drawing.

A simultaneous embedding with fixed edges (Sefe) of two planar graphs R and B is a pair of plane drawings of R and B that coincide when restricted to their common vertices and edges. We show that whenever R and B admit a Sefe, they also admit a Sefe in which every edge is a polygonal curve with few bends and every pair of edges has few crossings. Specifically: (1) if R and B are trees then one bend per edge and four crossings per edge pair suffice, (2) if R is a planar graph and B is a tree then six bends per edge and eight crossings per edge pair suffice, and (3) if R and B are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. This improves on results by Grilli et al. (GD’14), who prove that nine bends per edge suffice, and by Chan et al. (GD’14), who prove that twenty-four crossings per edge pair suffice.

Motivated by visualization of large graphs, we introduce a new type of graph drawing called “rook-drawing”. A rook-drawing of a graph G is obtained by placing the n nodes of G on the intersections of a regular grid, such that each row and column of the grid supports exactly one node. This paper focuses on rook-drawings of planar graphs. We first give a linear algorithm to compute a planar straight-line rook-drawing for outerplanar graphs. We then characterize the maximal planar graphs admitting a planar straight-line rook-drawing, which are unique for a given order. Finally, we give a linear time algorithm to compute a polyline planar rook-drawing for plane graphs with at most $$n-3$$ bent edges.

In a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by x-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with n characters, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with $$O(n\log n)$$ crossings. Furthermore, we show that there exist storylines in this restricted case that require $$\varOmega (n\log n)$$ crossings. Lastly, we show that, in the general case, minimizing the number of crossings in a storyline visualization is fixed-parameter tractable, when parameterized on the number of characters k. Our algorithm runs in time $$O(k!^2k\log k + k!^2m)$$, where m is the number of meetings.

In this paper, we show that there exist $$(6t-1)$$-regular graphs with thickness t, by constructing such an example graph. Since all graphs of thickness t must have at least one node with degree less than 6t, this construction is optimal. We also show, by construction, that there exist 5t-regular graphs with geometric thickness at most t. Our construction for the latter builds off of a relationship between geometric thickness and the Cartesian product of two graphs.

Let d and t be fixed positive integers, and let $$K^d_{t,\ldots ,t}$$ denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem of extremal hypergraph theory, due to Erdős [7], the number of hyperedges of a d-uniform hypergraph on n vertices that does not contain $$K^d_{t,\ldots ,t}$$ as a subhypergraph, is $$n^{d-\frac{1}{t^{d-1}}}$$. This bound is not far from being optimal.We address the same problem restricted to intersection hypergraphs of $$(d-1)$$-dimensional simplices in $$\mathbb {R}^d$$. Given an n-element set $$\mathcal {S}$$ of such simplices, let $$\mathcal {H}^d(\mathcal {S})$$ denote the d-uniform hypergraph whose vertices are the elements of $$\mathcal {S}$$, and a d-tuple is a hyperedge if and only if the corresponding simplices have a point in common. We prove that if $$\mathcal {H}^d(\mathcal {S})$$ does not contain $$K^d_{t,\ldots ,t}$$ as a subhypergraph, then its number of edges is O(n) if $$d=2$$, and $$O(n^{d-1+\epsilon })$$ for any $$\epsilon >0$$ if $$d \ge 3$$. This is almost a factor of n better than Erdős’s above bound. Our result is tight, apart from the error term $$\epsilon $$ in the exponent.In particular, for $$d=2$$, we obtain a theorem of Fox and Pach [8], which states that every $$K_{t,t}$$-free intersection graph of nsegments in the plane has O(n) edges. The original proof was based on a separator theorem that does not generalize to higher dimensions. The new proof works in any dimension and is simpler: it uses size-sensitive cuttings, a variant of random sampling. We demonstrate the flexibility of this technique by extending the proof of the planar version of the theorem to intersection graphs of x-monotone curves.

We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex u is represented by a geometric object R(u) and in which each edge (u, v) is represented by the intersection between R(u) and R(v) if it belongs to a dense subgraph or by a curve connecting the boundaries of R(u) and R(v) otherwise. We study a notion of planarity, called Clique Planarity, for intersection-link representations of graphs in which the dense subgraphs are cliques.

We consider arrangements of axis-aligned rectangles in the plane. A geometric arrangement specifies the coordinates of all rectangles, while a combinatorial arrangement specifies only the respective intersection type in which each pair of rectangles intersects. First, we investigate combinatorial contact arrangements, i.e., arrangements of interior-disjoint rectangles, with a triangle-free intersection graph. We show that such rectangle arrangements are in bijection with the 4-orientations of an underlying planar multigraph and prove that there is a corresponding geometric rectangle contact arrangement. Using this, we give a new proof that every triangle-free planar graph is the contact graph of such an arrangement. Secondly, we introduce the question whether a given rectangle arrangement has a combinatorially equivalent square arrangement. In addition to some necessary conditions and counterexamples, we show that rectangle arrangements pierced by a horizontal line are squarable under certain sufficient conditions.

The visual analysis of complex networks is a challenging task in many fields, such as systems biology or social sciences. Often, various domain experts work together to improve the analysis time or the quality of the analysis results. Collaborative visualization tools can facilitate the analysis process in such situations. We propose a new web-based visualization environment which supports distributed, synchronous and asynchronous collaboration. In addition to standard collaboration features like event tracking or synchronizing, our client/server-based system provides a rich set of visualization and interaction techniques for better navigation and overview of the input network. Changes made by specific analysts or even just visited network elements are highlighted on demand by heat maps. They enable us to visualize user behavior data without affecting the original graph visualization. We evaluate the usability of the heat map approach against two alternatives in a user experiment.

We provide a pipeline for generating syntax diagrams (also called railroad diagrams) from context free grammars. Syntax diagrams are a graphical representation of a context free language, which we formalize abstractly as a set of mutually recursive nondeterministic finite automata and draw by combining elements from the confluent drawing, layered drawing, and smooth orthogonal drawing styles. Within our pipeline we introduce several heuristics that modify the grammar but preserve the language, improving the aesthetics of the final drawing.

We present Kojaph, a new system for the visual definition and exploration of patterns in graph databases. It offers an expressive visual language integrated in a simple user interface, to define complex patterns as a combination of topological properties and node/edge attribute properties. Users can also interact with the query results and visually explore the graph incrementally, starting from such results. From the application perspective, Kojaph has been designed to run on top of every desired graph database management system (GDBMS). As a proof of concept, we integrated it with Neo4J, the most popular GDBMS.

In a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan-planar drawings such that the vertices are assigned to two distinct horizontal layers and edges are straight-line segments that connect vertices of different layers. We characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs.

IC-planar graphs are those graphs that admit a drawing where no two crossed edges share an end-vertex and each edge is crossed at most once. They are a proper subfamily of the 1-planar graphs. Given an embedded IC-planar graph G with n vertices, we present an O(n)-time algorithm that computes a straight-line drawing of G in quadratic area, and an $$O(n^3)$$-time algorithm that computes a straight-line drawing of G with right-angle crossings in exponential area. Both these area requirements are worst-case optimal. We also show that it is $$\mathrm {NP}$$-complete to test IC-planarity both in the general case and in the case in which a rotation system is fixed for the input graph. Furthermore, we describe a polynomial-time algorithm to test whether a set of matching edges can be added to a triangulated planar graph such that the resulting graph is IC-planar.

An abstract topological graph (briefly an AT-graph) is a pair $$A=(G,\mathcal {X})$$ where $$G=(V,E)$$ is a graph and $$\mathcal {X}\subseteq \left( {\begin{array}{c}E\\ 2\end{array}}\right) $$ is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from $$\mathcal {X}$$ crosses exactly once and no other pair crosses. We characterize simply realizable complete AT-graphs by a finite set of forbidden AT-subgraphs, each with at most six vertices. This implies a straightforward polynomial algorithm for testing simple realizability of complete AT-graphs, which simplifies a previous algorithm by the author.

In this paper we show how techniques developed for untangling planar graphs by Bose et al. [Discrete & Computational Geometry 42(4): 570–585 (2009)] and Goaoc et al. [Discrete & Computational Geometry 42(4): 542–569 (2009)] imply new results about some recent graph drawing models. These include column planarity, universal point subsets, and partial simultaneous geometric embeddings (with or without mappings). Some of these results answer open problems posed in previous papers.

The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process.In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.

A graph has strong convex dimension 2, if it admits a straight-line drawing in the plane such that its vertices are in convex position and the midpoints of its edges are also in convex position. Halman, Onn, and Rothblum conjectured that graphs of strong convex dimension 2 are planar and therefore have at most $$3n-6$$ edges. We prove that all such graphs have at most $$2n-3$$ edges while on the other hand we present a class of non-planar graphs of strong convex dimension 2. We also give lower bounds on the maximum number of edges a graph of strong convex dimension 2 can have and discuss variants of this graph class. We apply our results to questions about large convexly independent sets in Minkowski sums of planar point sets, that have been of interest in recent years.

An obstacle representation of a graph G is a set of points in the plane representing the vertices of G, together with a set of polygonal obstacles such that two vertices of G are connected by an edge in G if and only if the line segment between the corresponding points avoids all the obstacles. The obstacle number$${{\mathrm{obs}}}(G)$$ofG is the minimum number of obstacles in an obstacle representation of G.We provide the first non-trivial general upper bound on the obstacle number of graphs by showing that every n-vertex graph G satisfies $${{\mathrm{obs}}}(G) \le 2n\log {n}$$. This refutes a conjecture of Mukkamala, Pach, and Pálvölgyi. For bipartite n-vertex graphs, we improve this bound to $$n-1$$. Both bounds apply even when the obstacles are required to be convex. We also prove a lower bound $$2^{\varOmega (hn)}$$ on the number of n-vertex graphs with obstacle number at most h for $$h<n$$ and an asymptotically matching lower bound $$\varOmega (n^{4/3}M^{2/3})$$ for the complexity of a collection of $$M \ge \varOmega (n)$$ faces in an arrangement of $$n^2$$ line segments with 2n endpoints.

Let $$\mathcal {C}=\{C_1,\ldots , C_n\}$$ denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection $$\mathcal {C}$$ forms a visibility clique if for every $$i<j$$ the intersection $$C_i$$ and $$C_j$$ is not covered by the elements that are stacked between them, i.e., $$(C_i\cap C_j) \setminus \bigcup _{i<l<j}C_l\not =\emptyset $$.We show that if $$\mathcal {C}$$ forms a visibility clique its size is bounded from above by $$O(k^4)$$ thereby improving the upper bound of $$2^{2^{k}}$$ from the aforementioned paper. We also obtain an upper bound of $$2^{2\left( {\begin{array}{c}k\\ 2\end{array}}\right) +2}$$ on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gon.

Let R be a set of n red points and B be a set of n blue points in the Euclidean plane. We study the problem of computing a planar drawing of a cycle of minimum length that contains vertices at points $$R \cup B$$ and alternates colors. When these points are collinear, we describe a $$\varTheta (n \log n)$$-time algorithm to find such a shortest alternating cycle where every edge has at most two bends. We extend our approach to compute shortest alternating paths in $$O(n^2)$$ time with two bends per edge and to compute shortest alternating cycles on 3-colored point-sets in $$O(n^2)$$ time with O(n) bends per edge. We also prove that for arbitrary k-colored point-sets, the problem of computing an alternating shortest cycle is NP-hard, where k is any positive integer constant.

Set membership of points in the plane can be visualized by connecting corresponding points via graphical features, like paths, trees, polygons, ellipses. In this paper we study the bus embeddability problem (BEP): given a set of colored points we ask whether there exists a planar realization with one horizontal straight-line segment per color, called bus, such that all points with the same color are connected with vertical line segments to their bus. We present an ILP and an FPT algorithm for the general problem. For restricted versions of this problem, such as when the relative order of buses is predefined, or when a bus must be placed above all its points, we provide efficient algorithms. We show that another restricted version of the problem can be solved using 2-stack pushall sorting. On the negative side we prove the NP-completeness of a special case of BEP.

A point set $$S \subseteq \mathbb {R}^2$$ is universal for a class $$\mathcal G$$ if every graph of $$\mathcal{G}$$ has a planar straight-line embedding on S. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a sub-quadratic universal point set for them is one of the most fascinating open problems in Graph Drawing. Motivated by the fact that outerplanarity is a key property for the existence of small universal point sets, we study 2-outerplanar graphs and provide for them a universal point set of size $$O(n \log n)$$.

For every integer $$n\ge 4$$, we construct a planar point set $$S_n$$ of size $$6n-10$$ such that every n-vertex planar graph G admits a plane embedding in which the vertices are mapped to points in $$S_n$$, and every edge is either a line segment or a polyline with one bend, where the bend point is also in $$S_n$$.

Disk contact representations realize graphs by mapping vertices bijectively to interior-disjoint disks in the plane such that two disks touch each other if and only if the corresponding vertices are adjacent in the graph. Deciding whether a vertex-weighted planar graph can be realized such that the disks’ radii coincide with the vertex weights is known to be $$\textsf {NP}$$-hard. In this work, we reduce the gap between hardness and tractability by analyzing the problem for special graph classes. We show that it remains $$\textsf {NP}$$-hard for outerplanar graphs with unit weights and for stars with arbitrary weights, strengthening the previous hardness results. On the positive side, we present constructive linear-time recognition algorithms for caterpillars with unit weights and for embedded stars with arbitrary weights.

We wish to decide whether a simply connected flexible polygonal structure can be realized in Euclidean space. Two models are considered: polygonal linkages (body-and-joint framework) and contact graphs of unit disks in the plane. (1) We show that it is strongly NP-hard to decide whether a given polygonal linkage is realizable in the plane when the bodies are convex polygons and their contact graph is a tree; the problem is weakly NP-hard already for a chain of rectangles, but efficiently decidable for a chain of triangles hinged at distinct vertices. (2) We also show that it is strongly NP-hard to decide whether a given tree is the contact graph of interior-disjoint unit disks in the plane.

Let $$\mathcal {G} $$ be a plane triangulated graph. A rectangular dual of $$\mathcal {G} $$ is a partition of a rectangle R into a set $$\mathcal {R} $$ of interior-disjoint rectangles, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge. A rectangular dual is sliceable if it can be recursively subdivided along horizontal or vertical lines. A graph is rectangular if it has a rectangular dual and sliceable if it has a sliceable rectangular dual. There is a clear characterization of rectangular graphs. However, a full characterization of sliceable graphs is still lacking. The currently best result (Yeap and Sarrafzadeh, 1995) proves that all rectangular graphs without a separating 4-cycle are sliceable. In this paper we introduce a recursively defined class of graphs and prove that these graphs are precisely the nonsliceable graphs with exactly one separating 4-cycle.

We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose cells we call pixels in 2D and voxels in 3D. Two pixels are adjacent if they share an edge, two voxels if they share a face. We call a connected set of pixels or voxels a blob. Given a graph, we represent its vertices by disjoint blobs such that two blobs contain adjacent pixels or voxels if and only if the corresponding vertices are adjacent. We are interested in the size of a representation, which is the number of pixels or voxels it consists of.We first show that finding minimum-size representations is NP-complete. Then, we bound representation sizes needed for certain graph classes. In 2D, we show that, for k-outerplanar graphs with n vertices, $$\varTheta (kn)$$ pixels are always sufficient and sometimes necessary. In particular, outerplanar graphs can be represented with a linear number of pixels, whereas general planar graphs sometimes need a quadratic number. In 3D, $$\varTheta (n^2)$$ voxels are always sufficient and sometimes necessary for any n-vertex graph. We improve this bound to $$\varTheta (n\cdot \tau )$$ for graphs of treewidth $$\tau $$ and to $$O((g+1)^2n\log ^2n)$$ for graphs of genus g. In particular, planar graphs admit representations with $$O(n\log ^2n)$$ voxels.

Homophily is a concept in social network analysis that states that in a network a link is more probable, if the two individuals have a common characteristic. We study the question if an observer can assess homophily by looking at the node-link diagram of the network. We design an experiment that investigates three different layout algorithms and asks the users to estimate the degree of homophily in the displayed network. One of the layout algorithms is a classical force-directed method, the other two are designed to improve node distinction based on the common characteristic. We study how each of the three layout algorithms helps to get a fair estimate, and whether there is a tendency to over or underestimate the degree of homophily. The stimuli in our experiments use different network sizes and different proportions of the cluster sizes.

We propose a new family of quality metrics for graph drawing; in particular, we concentrate on larger graphs. We illustrate these metrics with examples and apply the metrics to data from previous experiments, leading to the suggestion that the new metrics are effective.

Boundary labeling deals with annotating features in images such that labels are placed outside of the image and are connected by curves (so-called leaders) to the corresponding features. While boundary labeling has been extensively investigated from an algorithmic perspective, the research on its readability has been neglected. In this paper we present the first formal user study on the readability of boundary labeling. We consider the four most studied leader types with respect to their performance, i.e., whether and how fast a viewer can assign a feature to its label and vice versa. We give a detailed analysis of the results regarding the readability of the four models and discuss their aesthetic qualities based on the users’ preference judgments and interviews.

This report describes the 22nd Annual Graph Drawing Contest, held in conjunction with the 23rd International Symposium on Graph Drawing (GD’15) in Los Angeles, California, United States of America. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology.

The Organizing Committee of GD 2015 hosted a gradate workshop, continuing the tradition of previous Symposia, focusing on open problems in graph drawing.

A visibility drawing$$\varGamma $$ of a planar graph G maps the vertices into non-overlapping horizontal segments (bars), and the edges into vertical segments (visibilities), each connecting the two bars corresponding to its two end-vertices.

A map graph is a contact graph of internally-disjoint regions of the plane, where the contact can be even a point. Namely, each vertex is represented by a simple connected region and two vertices are connected by an edge iff the corresponding regions touch.

Partial edge drawing (PED) is a model for a straight-line drawing of a graph, where edges are subdivided into three parts in order to drop the middle part.

The world is a dynamic place, so when we use graphs to help understand real world problems the structure of such graphs inevitably changes over time. Understanding this change is important, but often challenging. Techniques for general purpose dynamic graph visualizations generally fall into one of two broad categories: animation or timeline based techniques [2]. Simple approaches using animation or small multiples experience challenges with change blindness and “preserving the user’s mental map” [1]. Storyline visualization techniques [5, 7] hold promise, though these techniques were not originally designed as general purpose solutions for dynamic graph visualization.

In 1963, Knuth published the first paper on a computer algorithm for a graph drawing problem, entitled “Computer-drawn Flowcharts” [8]. In this paper, Knuth describes an algorithm that takes as input an n-vertex directed graph G that represents a flowchart and, using the modern language of graph drawing, produces an orthogonal drawing of G.

Gestalt principles are rules for the organization of perceptual scenes. They were introduced in the context of philosophy and psychology in the 19th century and were used to define principles of human perception in the early 20th century. The Gestalt (form, in German) principles include, among others: proximity, the grouping of closely positioned objects; similarity, the grouping of objects of similar shape or color; continuation, the grouping of objects that form a continuous pattern; and symmetry, the grouping of objects that form symmetric patterns. Gestalt principles have been extensively applied in user interface design, graphic design, and information visualization.

We introduce a new gesture-based user interface for drawing graphs that recognizes specific body gestures using the Microsoft Kinect sensor. Our preliminary user study demonstrates the potential for using gesture-based interfaces in graph drawing.

We show that every planar straight line graph (PSLG) with n vertices can be augmented to a 2-edge-connected PSLG with the addition of at most $$\lfloor (4n-4)/3\rfloor $$ new edges. This bound is the best possible.