Graph Drawing and Network Visualization

The wide availability of powerful and inexpensive cloud computing services naturally motivates the study of distributed graph layout algorithms, able to scale to very large graphs. Nowadays, to process Big Data, companies are increasingly relying on PaaS infrastructures rather than buying and maintaining complex and expensive hardware. So far, only a few examples of basic force-directed algorithms that work in a distributed environment have been described. Instead, the design of a distributed multilevel force-directed algorithm is a much more challenging task, not yet addressed. We present the first multilevel force-directed algorithm based on a distributed vertex-centric paradigm, and its implementation on Giraph, a popular platform for distributed graph algorithms. Experiments show the effectiveness and the scalability of the approach. Using an inexpensive cloud computing service of Amazon, we draw graphs with ten million edges in about 60 min.

Force-directed layout methods constitute the most common approach to draw general graphs. Among them, stress minimization produces layouts of comparatively high quality but also imposes comparatively high computational demands. We propose a speed-up method based on the aggregation of terms in the objective function. It is akin to aggregate repulsion from far-away nodes during spring embedding but transfers the idea from the layout space into a preprocessing phase. An initial experimental study informs a method to select representatives, and subsequent more extensive experiments indicate that our method yields better approximations of minimum-stress layouts in less time than related methods.

Node overlap removal is a necessary step in many scenarios including laying out a graph, or visualizing a tag cloud. Our contribution is a new overlap removal algorithm that iteratively builds a Minimum Spanning Tree on a Delaunay triangulation of the node centers and removes the node overlaps by “growing” the tree. The algorithm is simple to implement yet produces high quality layouts. According to our experiments it runs several times faster than the current state-of-the-art methods.

We consider the problem of placing arrow heads in directed graph drawings without them overlapping other drawn objects. This gives drawings where edge directions can be deduced unambiguously. We show hardness of the problem, present exact and heuristic algorithms, and report on a practical study.

Bundling of graph edges (node-to-node connections) is a common technique to enhance visibility of overall trends in the edge structure of a large graph layout, and a large variety of bundling algorithms have been proposed. However, with strong bundling, it becomes hard to identify origins and destinations of individual edges. We propose a solution: we optimize edge coloring to differentiate bundled edges. We quantify strength of bundling in a flexible pairwise fashion between edges, and among bundled edges, we quantify how dissimilar their colors should be by dissimilarity of their origins and destinations. We solve the resulting nonlinear optimization, which is also interpretable as a novel dimensionality reduction task. In large graphs the necessary compromise is whether to differentiate colors sharply between locally occurring strongly bundled edges (“local bundles”), or also between the weakly bundled edges occurring globally over the graph (“global bundles”); we allow a user-set global-local tradeoff. We call the technique “peacock bundles”. Experiments show the coloring clearly enhances comprehensibility of graph layouts with edge bundling.

Visualizing hypergraphs, systems of subsets of some universe, has continuously attracted research interest in the last decades. We study a natural kind of hypergraph visualization called subdivision drawings. Dinkla et al. [Comput. Graph. Forum ’12] claimed that only few hypergraphs have a subdivision drawing. However, this statement seems to be based on the assumption (also used in previous work) that the input hypergraph does not contain twins, pairs of vertices which are in precisely the same hyperedges (subsets of the universe). We show that such vertices may be necessary for a hypergraph to admit a subdivision drawing. As a counterpart, we show that the number of such “necessary twins” is upper-bounded by a function of the number m of hyperedges and a further parameter r of the desired drawing related to its number of layers. This leads to a linear-time algorithm for determining such subdivision drawings if m and r are constant; in other words, the problem is linear-time fixed-parameter tractable with respect to the parameters m and r.

We study a problem proposed by Hurtado et al. [10] motivated by sparse set visualization. Given n points in the plane, each labeled with one or more primary colors, a colored spanning graph (CSG) is a graph such that for each primary color, the vertices of that color induce a connected subgraph. The Min-CSG problem asks for the minimum sum of edge lengths in a colored spanning graph. We show that the problem is NP-hard for k primary colors when $$k\ge 3$$ and provide a $$(2-\frac{1}{3+2\varrho })$$-approximation algorithm for $$k=3$$ that runs in polynomial time, where $$\varrho $$ is the Steiner ratio. Further, we give a O(n) time algorithm in the special case that the input points are collinear and k is constant.

We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.

NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and inter-cluster edges as curves connecting the matrix boundaries. We study the complexity of constructing NodeTrix representations focusing on planarity testing problems, and we show several $$\mathbb {NP}$$-completeness results and some polynomial-time algorithms.

It is proved that every series-parallel digraph whose maximum vertex-degree is $$\varDelta $$ admits an upward planar drawing with at most one bend per edge such that each edge segment has one of $$\varDelta $$ distinct slopes. This is shown to be worst-case optimal in terms of the number of slopes. Furthermore, our construction gives rise to drawings with optimal angular resolution $$\frac{\pi }{\varDelta }$$. A variant of the proof technique is used to show that (non-directed) reduced series-parallel graphs and flat series-parallel graphs have a (non-upward) one-bend planar drawing with $$\lceil \frac{\varDelta }{2}\rceil $$ distinct slopes if biconnected, and with $$\lceil \frac{\varDelta }{2}\rceil +1$$ distinct slopes if connected.

A non-aligned drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. showed that not all planar graphs have a non-aligned planar straight-line drawing in the $$n\times n$$-grid. They also showed that such a drawing exists if up to $$n-3$$ edges may have a bend.In this paper, we give algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, we give such drawings in an $$n\times n$$-grid with at most $$\frac{2n-5}{3}$$ bends, and we study what grid-size can be achieved if we insist on having straight-line drawings.

In geographic information systems and in the production of digital maps for small devices with restricted computational resources one often wants to round coordinates to a rougher grid. This removes unnecessary detail and reduces space consumption as well as computation time. This process is called snapping to the grid and has been investigated thoroughly from a computational-geometry perspective. In this paper we investigate the same problem for given drawings of planar graphs under the restriction that their combinatorial embedding must be kept and edges are drawn straight-line. We show that the problem is NP-hard for several objectives and provide an integer linear programming formulation. Given a plane graph G and a positive integer w, our ILP can also be used to draw G straight-line on a grid of width w and minimum height (if possible).

Given a planar graph G, what is the maximum number of collinear vertices in a planar straight-line drawing of G? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known: Every n-vertex planar graph has a planar straight-line drawing with $$\varOmega (\sqrt{n})$$ collinear vertices; for every n, there is an n-vertex planar graph whose every planar straight-line drawinghas $$O(n^{0.986})$$ collinear vertices; every n-vertex planar graph of treewidth at most two has a planar straight-line drawingwith $$\varTheta (n)$$ collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs, partially answering two problems posed by Ravsky and Verbitsky. Similar results are not possible for all bounded treewidth or bounded degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems.

We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows.We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.

We study the problem of visualizing phylogenetic networks, which are extensions of the Tree of Life in biology. We use a space filling visualization method, called DAGmaps, in order to obtain clear visualizations using limited space. In this paper, we restrict our attention to galled trees and galled networks and present linear time algorithms for visualizing them as DAGmaps.

The Directed Layering Problem (DLP) solves a step of the widely used layer-based approach to automatically draw directed acyclic graphs. To cater for cyclic graphs, usually a preprocessing step is used that solves the Feedback Arc Set Problem (FASP) to make the graph acyclic before a layering is determined.Here we present the Generalized Layering Problem (GLP), which solves the combination of DLP and FASP simultaneously, allowing general graphs as input. We present an integer programming model and a heuristic to solve the NP-complete GLP and perform thorough evaluations on different sets of graphs and with different implementations for the steps of the layer-based approach.We observe that GLP reduces the number of dummy nodes significantly, can produce more compact drawings, and improves on graphs where DLP yields poor aspect ratios.

We consider the problem of layering general directed graphs under height and possibly also width constraints. Given a directed graph $$G=(V,A)$$ and a maximal height, we propose a layering approach that minimizes a weighted sum of the number of reversed arcs, the arc lengths, and the width of the drawing. We call this the Compact Generalized Layering Problem (CGLP). Here, the width of a drawing is defined as the maximum sum of the number of vertices placed on a layer and the number of dummy vertices caused by arcs traversing the layer. The CGLP is $$\mathcal {NP}$$-hard. We present two MIP models for this problem. The first one (EXT) is our extension of a natural formulation for directed acyclic graphs as suggested by Healy and Nikolov. The second one (CGL) is a new formulation based on partial orderings. Our computational experiments on two benchmark sets show that the CGL formulation can be solved much faster than EXT using standard commercial MIP solvers. Moreover, we suggest a variant of CGL, called MML, that can be seen as a heuristic approach. In our experiments, MML clearly improves on CGL in terms of running time while it does not considerably increase the average arc lengths and widths of the layouts although it solves a slightly different problem where the dummy vertices are not taken into account.

Canonical orderings serve as the basis for many incremental planar drawing algorithms. All these techniques, however, have in common that they are limited to undirected graphs. While st-orderings do extend to directed graphs, especially planar st-graphs, they do not offer the same properties as canonical orderings. In this work we extend the so called bitonic st-orderings to directed graphs. We fully characterize planar st-graphs that admit such an ordering and provide a linear-time algorithm for recognition and ordering. If for a graph no bitonic st-ordering exists, we show how to find in linear time a minimum set of edges to split such that the resulting graph admits one. With this new technique we are able to draw every upward planar graph on n vertices by using at most one bend per edge, at most $$n - 3$$ bends in total and within quadratic area.

We consider the recently introduced model of low ply graph drawing, in which the ply-disks of the vertices do not have many common overlaps, which results in a good distribution of the vertices in the plane. The ply-disk of a vertex in a straight-line drawing is the disk centered at it whose radius is half the length of its longest incident edge. The largest number of ply-disks having a common overlap is called the ply-number of the drawing.We focus on trees. We first consider drawings of trees with constant ply-number, proving that they may require exponential area, even for stars, and that they may not even exist for bounded-degree trees. Then, we turn our attention to drawings with logarithmic ply-number and show that trees with maximum degree 6 always admit such drawings in polynomial area.

We initiate the study of 2.5D box visibility representations (2.5D-BR) where vertices are mapped to 3D boxes having the bottom face in the plane $$z=0$$ and edges are unobstructed lines of sight parallel to the x- or y-axis. We prove that: (i) Every complete bipartite graph admits a 2.5D-BR; (ii) The complete graph $$K_n$$ admits a 2.5D-BR if and only if $$n \leqslant 19$$; (iii) Every graph with pathwidth at most 7 admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBR) which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an n-vertex graph that admits a 2.5D-GBR has at most $$4n - 6 \sqrt{n}$$ edges and this bound is tight. Finally, we prove that deciding whether a given graph G admits a 2.5D-GBR with a given footprint is NP-complete. The footprint of a 2.5D-BR $$\varGamma $$ is the set of bottom faces of the boxes in $$\varGamma $$.

For a graph G, a function $$\psi $$ is called a bar visibility representation of G when for each vertex $$v \in V(G)$$, $$\psi (v)$$ is a horizontal line segment (bar) and $$uv \in E(G)$$ iff there is an unobstructed, vertical, $$\varepsilon $$-wide line of sight between $$\psi (u)$$ and $$\psi (v)$$. Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation $$\psi $$ of G, additionally, for each directed edge (u, v) of G, puts the bar $$\psi (u)$$ strictly below the bar $$\psi (v)$$. We study a generalization of the recognition problem where a function $$\psi '$$ defined on a subset $$V'$$ of V(G) is given and the question is whether there is a bar visibility representation $$\psi $$ of G with $$\psi |V' = \psi '$$. We show that for undirected graphs this problem together with closely related problems are $$\mathsf {NP}$$-complete, but for certain cases involving directed graphs it is solvable in polynomial time.

An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. Namely, we prove that if G is 1-plane (i.e., it has at most one crossing per edge) an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute in O(n) time an OPVR of G whose vertex complexity is bounded by a constant. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be $$\varOmega (n)$$. In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed. Finally, we present the results of an experimental study on the vertex complexity of OPVRs of 1-plane graphs.

Obstacle representations of graphs have been investigated quite intensely over the last few years. We focus on graphs that can be represented by a single obstacle. Given a (topologically open) non-self-intersecting polygon C and a finite set P of points in general position in the complement of C, the visibility graph$$G_C(P)$$ has a vertex for each point in P and an edge pq for any two points p and q in P that can see each other, that is, $$\overline{pq} \cap C=\emptyset $$. We draw $$G_C(P)$$ straight-line and call this a visibility drawing. Given a graph G, we want to compute an obstacle representation of G, that is, an obstacle C and a set of points P such that $$G=G_C(P)$$. The complexity of this problem is open, even when the points are exactly the vertices of a simple polygon and the obstacle is the complement of the polygon—the simple-polygon visibility graph problem.There are two types of obstacles; outside obstacles lie in the unbounded component of the visibility drawing, whereas inside obstacles lie in the complement of the unbounded component. We show that the class of graphs with an inside-obstacle representation is incomparable with the class of graphs that have an outside-obstacle representation. We further show that any graph with at most seven vertices has an outside-obstacle representation, which does not hold for a specific graph with eight vertices. Finally, we show NP-hardness of the outside-obstacle graph sandwich problem: given graphs G and H on the same vertex set, is there a graph K such that $$G \subseteq K \subseteq H$$ and K has an outside-obstacle representation. Our proof also shows that the simple-polygon visibility graph sandwich problem, the inside-obstacle graph sandwich problem, and the single-obstacle graph sandwich problem are all NP-hard.

We prove that if an n-vertex graph G can be drawn in the plane such that each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints, then G has O(n) edges. Graphs that admit such drawings are related to quasi-planar graphs and to maximal 1-planar and fan-planar graphs.

Thomassen characterized some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph is drawable in straight-lines if and only if it does not contain the configuration [C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory, 10(3), 335–341, 1988].In this paper, we characterize some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Re-embedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration.

A graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC (Right Angle Crossing) if the edges cross only at right angles. The relationships between 1-planar graphs and RAC drawings have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC drawable and graphs that have a straight-line RAC drawing but that are not 1-planar [22]. Also, straight-line RAC drawings always exist for IC-planar graphs [9], a subclass of 1-planar graphs. One of the main questions still open is whether every 1-planar graph has a RAC drawing with at most one bend per edge. We positively answer this question.

A k-planar graph is a graph that can be drawn in the plane such that every edge is crossed at most k times. For $$k \le 4$$, Pach and Tóth [20] proved a bound of $$(k+3)(n-2)$$ on the total number of edges of a k-planar graph, which is tight for $$k=1,2$$. For $$k=3$$, the bound of $$6n-12$$ has been improved to $$\frac{11}{2}n-11$$ in [19] and has been shown to be optimal up to an additive constant for simple graphs. In this paper, we prove that the bound of $$\frac{11}{2}n-11$$ edges also holds for non-simple 3-planar graphs that admit drawings in which non-homotopic parallel edges and self-loops are allowed. Based on this result, a characterization of optimal 3-planar graphs (that is, 3-planar graphs with n vertices and exactly $$\frac{11}{2}n-11$$ edges) might be possible, as to the best of our knowledge the densest known simple 3-planar is not known to be optimal.

Given a graph G, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of G with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but—to the best of our knowledge—they have never been compared competitively in practice.We report on an exploratory study on the relative merits of the diverse approaches, focusing on practical runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the building block of the strongest choice.

A storyline visualization is a layout that represents the temporal dynamics of social interactions along time by the convergence of chronological lines. Among the criteria oriented at improving aesthetics and legibility of a representation of this type, a small number of line crossings is the hardest to achieve. We model the crossing minimization in the storyline visualization problem as a multi-layer crossing minimization problem with tree constraints. Our algorithm can compute a layout with the minimum number of crossings of the chronological lines. Computational results demonstrate that it can solve instances with more than 100 interactions and with more than 100 chronological lines to optimality.

Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines.Our main results are as follows. We show that minimizing the number of block crossings is NP-hard, and we develop, for meetings of bounded size, a constant-factor approximation. We also present two fixed-parameter algorithms and, for meetings of size 2, a greedy heuristic that we evaluate experimentally.

We study the algorithmic aspect of edge bundling. A bundled crossing in a drawing of a graph is a group of crossings between two sets of parallel edges. The bundled crossing number is the minimum number of bundled crossings that group all crossings in a drawing of the graph.We show that the bundled crossing number is closely related to the orientable genus of the graph. If multiple crossings and self-intersections of edges are allowed, the two values are identical; otherwise, the bundled crossing number can be higher than the genus.We then investigate the problem of minimizing the number of bundled crossings. For circular graph layouts with a fixed order of vertices, we present a constant-factor approximation algorithm. When the circular order is not prescribed, we get a $$\frac{6c}{c-2}$$-approximation for a graph with n vertices having at least cn edges for $$c>2$$. For general graph layouts, we develop an algorithm with an approximation factor of $$\frac{6c}{c-3}$$ for graphs with at least cn edges for $$c > 3$$.

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph $$G, \text {cr}(G)$$, is the minimum number of pairs of crossing edges in any straight-line drawing of G. Determining or estimating $$\overline{\mathrm{cr}}(G)$$ appears to be a difficult problem, and deciding if $$\overline{\mathrm{cr}}(G)\le k$$ is known to be NP-hard. In fact, the asymptotic behavior of $$\overline{\mathrm{cr}}(K_n)$$ is still unknown.In this paper, we present a deterministic $$n^{2+o(1)}$$-time algorithm that finds a straight-line drawing of any n-vertex graph G with $$\overline{\mathrm{cr}}(G) + o(n^4)$$ pairs of crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense n-vertex graph G, one can efficiently find a straight-line drawing of G with $$(1 + o(1))\overline{\mathrm{cr}}(G)$$ pairs of crossing edges.

Motivated by a problem asked by Richter and by the long standing Harary-Hill conjecture, we study the relation between the crossing number of a graph G and the crossing number of its cone CG, the graph obtained from G by adding a new vertex adjacent to all the vertices in G. Simple examples show that the difference $$cr(CG)-cr(G)$$ can be arbitrarily large for any fixed $$k=cr(G)$$. In this work, we are interested in finding the smallest possible difference, that is, for each non-negative integer k, find the smallest f(k) for which there exists a graph with crossing number at least k and cone with crossing number f(k). For small values of k, we give exact values of f(k) when the problem is restricted to simple graphs, and show that $$f(k)=k+\varTheta (\sqrt{k})$$ when multiple edges are allowed.

Topological drawings are natural representations of graphs in the plane, where vertices are represented by points, and edges by curves connecting the points. We consider a natural class of simple topological drawings of complete bipartite graphs, in which we require that one side of the vertex set bipartition lies on the outer boundary of the drawing. We investigate the combinatorics of such drawings. For this purpose, we define combinatorial encodings of the drawings by enumerating the distinct drawings of subgraphs isomorphic to $$K_{2,2}$$ and $$K_{3,2}$$, and investigate the constraints they must satisfy. We prove in particular that for complete bipartite graphs of the form $$K_{2,n}$$ and $$K_{3,n}$$, such an encoding corresponds to a drawing if and only if it obeys consistency conditions on triples and quadruples. In the general case of $$K_{k,n}$$ with $$k\ge 2$$, we completely characterize and enumerate drawings in which the order of the edges around each vertex is the same for vertices on the same side of the bipartition.

We reprove the strong Hanani–Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely on the characterization of forbidden minors, which gives hope to extend it to other surfaces. Moreover, our approach can be used to provide an efficient algorithm turning a Hanani–Tutte drawing on the projective plane into an embedding.

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. A pair of edges e and f in a graph is independent if e and f do not share a vertex.We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing.

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity, are polynomial-time solvable.Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels.

We show that testing whether a given graph has a 3-track layout is hard, by characterizing the bipartite 3-track graphs in terms of leveled planarity. Additionally, we investigate the parameterized complexity of track layouts, showing that past methods used for book layouts do not work to parameterize the problem by treewidth or almost-tree number but that the problem is (non-uniformly) fixed-parameter tractable for tree-depth. We also provide several natural classes of bipartite planar graphs, including the bipartite outerplanar graphs, squaregraphs, and dual graphs of arrangements of monotone curves, that always have 3-track layouts.

It is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as planar graphs and graphs of bounded genus, many other graph families are not closed under taking minors. For fixed g and k, we show that every n-vertex graph that can be embedded on a surface of genus g with at most k crossings per edge has stack-number $$\mathcal {O}(\log n)$$; this includes k-planar graphs. The previously best known bound for the stack-number of these families was $$\mathcal {O}(\sqrt{n})$$, except in the case of 1-planar graphs. Analogous results are proved for map graphs that can be embedded on a surface of fixed genus. None of these families is closed under taking minors. The main ingredient in the proof of these results is a construction proving that n-vertex graphs that admit constant layered separators have $$\mathcal {O}(\log n)$$ stack-number.

A geometric graph is angle-monotone if every pair of vertices has a path between them that—after some rotation—is x- and y-monotone. Angle-monotone graphs are $$\sqrt{2}$$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone—specifically, we prove that the half-$$\theta _6$$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within $$1 + \sqrt{2}$$ times the Euclidean distance from s to t. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.

We introduce and study the $${\textsc {OrthoSEFE}\text {-}{k}} $$ problem: Given k planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the k graphs? We show that the problem is NP-complete for $$k \ge 3$$ even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for $$k \ge 2$$ even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for $$k=2$$ when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge.

We study the following problem: Given k paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction? We prove that, for any dimension d, there is a set of $$d+1$$ paths that does not admit a monotone simultaneous geometric embedding.

Several techniques for visualization of dynamic graphs are based on different spatial arrangements of a temporal sequence of node-link diagrams. Many studies in the literature have investigated the importance of maintaining the user’s mental map across this temporal sequence, but usually each layout is considered as a static graph drawing and the effect of user interaction is disregarded. We conducted a task-based controlled experiment to assess the effectiveness of two basic interaction techniques: the adjustment of the layout stability and the highlighting of adjacent nodes and edges. We found that generally both interaction techniques increase accuracy, sometimes at the cost of longer completion times, and that the highlighting outclasses the stability adjustment for many tasks except the most complex ones.

While the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a document production workflow and algorithmic approaches only rarely take temporal information into consideration. During the production of a presentation or a paper, most users will visualize how, say, a search tree evolves over time by manually drawing a sequence of trees. We present an extension of the popular typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running on the documents then results in documents in the svg format with visually pleasing embedded animations. Our algorithm produces animations that satisfy a set of natural aesthetic criteria when possible. On the negative side, we show that one cannot always satisfy all criteria simultaneously and that minimizing their violations is NP-complete.

This report describes the 23rd Annual Graph Drawing Contest, held in conjunction with the 24th International Symposium on Graph Drawing (GD’16) in Athens, Greece. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology.