A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> Given a planar graph G together with a planar representation P, a region preserving grid embedding of G is a planar embedding of G in the rectilinear grid that has planar representation isomorphic to P. In this paper, an algorithm is presented that computes a region preserving grid embedding with the minimum number of bends in edges. This algorithm makes use of network flow techniques, and runs in time $O(n^2 \log n)$, where n is the number of vertices of the graph. Constrained versions of the problem are also considered, and most results are extended to k-gonal graphs, i.e., graphs whose edges are sequences of segments with slope multiple of ${{180} / k}$ degrees. Applications of the above results can be found in several areas: VLSI circuit layout, architectural design, communication by light or microwave, transportation problems, and automatic layout of graphlike diagrams. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> Networks are critical to modern society, and a thorough understanding of how they behave is crucial to their efficient operation. Fortunately, data on networks is plentiful; by visualizing this data, it is possible to greatly improve our understanding. Our focus is on visualizing the data associated with a network and not on simply visualizing the structure of the network itself. We begin with three static network displays; two of these use geographical relationships, while the third is a matrix arrangement that gives equal emphasis to all network links. Static displays can be swamped with large amounts of data; hence we introduce direct manipulation techniques that permit the graphs to continue to reveal relationships in the context of much more data. In effect, the static displays are parameterized so that interesting views may easily be discovered interactively. The software to carry out this network visualization is called SeeNet. > <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> Graphs are typically visualized as node-link diagrams. Although there is a fair amount of research focusing on crossing minimization to improve readability, little attention has been paid on how to handle crossings when they are an essential part of the final visualizations. This requires us to understand how people read graphs and how crossings affect reading performance. As an initial step to this end, a preliminary eye tracking experiment was conducted. The specific purpose of this experiment was to test the effects of crossing angles and geometric-path tendency on eye movements and performance. Sixteen subjects performed both path search and node locating tasks with six drawings. The results showed that small angles can slow down and trigger extra eye movements, causing delays for path search tasks, whereas crossings have little impact on node locating tasks. Geometric-path tendency indicates that a path between two nodes can become harder to follow when many branches of the path go toward the target node. The insights obtained are discussed with a view to further confirmation in future work. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> In visualizing graphs as node-link diagrams, it is commonly accepted and employed as a general rule that the number of link crossings should be minimized whenever possible. However, little attention has been paid to how to handle the remaining crossings in the visualization. The study presented in this paper examines the effects of crossing angles on performance of path tracing tasks. It was found that the effect varied with the size of crossing angles. In particular, task response time decreased as the crossing angle increased. However, the rate of the decrease tended to level off when the angle was close to 90 degrees. One of the implications of this study in graph visualization is that just minimizing the crossing number is not sufficient to reduce the negative impact to the minimum. The angles of remaining crossings should be maximized as well. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> Recent empirical research has shown that increasing the angle of crossings reduces the effect of crossings and improves human readability [5]. In this paper, we introduce a post-processing algorithm, namely MAXCIR, that aims to increase crossing angles of circular layouts by using Quadratic Programming. Experimental results indicate that our method significantly increases crossing angles compared to the traditional equal-spacing algorithm, and that the running time is fairly negligible. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> This paper studies the problem of designing graph drawing algorithms that guarantee good trade-offs in terms of number of edge crossings, crossing angle resolution, and geodesic edge tendency. It describes two heuristics designed within the topology-driven force-directed framework that combines two classical graph drawing approaches: the force-directed approach and a planarization-based approach (e.g., the topology-shape-metrics approach). An extensive experimental analysis on two different test suites of graphs shows the effectiveness of the proposed solutions for the optimization of some readability metrics. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> A great deal of real-world data have graph structures, and such structures are often visualized into node-link diagrams for a better understanding of the data. Aesthetic criteria have been used as quality measures to evaluate the effectiveness of graph visualizations in conveying the embedded information to end users. However, commonly applied aesthetics are originally proposed based on common senses and personal intuitions; thus, their relevance to effectiveness is not guaranteed. It has been agreed that aesthetics should be established based on empirical evidence and derived from theories of how people read graphs. As the first step to this end, we have conducted two eye tracking studies in an attempt to understand the underlying mechanism of edge crossings, the most discussed aesthetic, affecting human graph reading performance. These studies lead to the findings of an important aesthetic of crossing angles and a graph reading behavior of geodesic path tendency. We demonstrate that eye tracking is an effective method for gaining insights into how people read graphs and that how aesthetics can be established based on human graph reading behavior. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> Web site traffic analysis studies how different pages forming Web sites are accessed by their target audience over time. From a business intelligence point of view, it represents one of the key activities for many private companies and public institutions. Recent papers pointed out that Web site traffic analysis is especially useful if it focuses on the user interest into the relevant concepts described in a Web site rather than counting user accesses to the distinct pages forming the Web site. This paper extends existing measures of conceptual Web site traffic analysis and describes a new system that supports this analysis by means of graph visualization techniques. The graph drawing engine of the system is a force-directed heuristic that computes a simultaneous embedding of two suitably defined graphs, that are non-planar in general. The heuristic is especially designed to take into account two important aesthetic criteria of the drawing: crossing resolution and geodesic edge tendency. We also present some experiments and case studies to show the effectiveness of the proposed approach in practice. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> The crossing-angle resolution of a drawing of a graph measures the smallest angle formed by any pair of crossing edges. In this chapter, we survey some of the most recent results and discuss the current research agenda on drawings of graphs with good crossing-angle resolution. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> One of the main principles for the effective visualization of graphs is the avoidance of edge crossings. Around this problem, very active research has been performed with works ranging from combinatorics, to algorithmics, visualization effects, to psychological user studies. Recently, the pragmatic approach has been proposed to avoid crossings by drawing the edges only partially. Unfortunately, no formal model and efficient algorithms have been formulated to this end. We introduce the concept for drawings of graphs with partially drawn edges (PED). Therefore we consider graphs with and without given embedding and characterize PEDs with concepts like symmetry and homogeneity. For graphs without embedding we formulate a sufficient condition to guarantee a symmetric homogeneous PED, and identify a nontrivial graph class which has a symmetric homogeneous PED. For graphs with given layout we consider the variants of maximizing the shortest partially drawn edge and the total length respectively. <s> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> Many automatic graph drawing algorithms implement only one or two aesthetic criteria since most aesthetics conflict with each other. Empirical research has shown that although those algorithms are based on different aesthetics, drawings produced by them have comparable effectiveness.The comparable effectiveness raises a question about the necessity of choosing one algorithm against another for drawing graphs when human performance is a main concern. In this paper, we argue that effectiveness can be improved when algorithms are designed by making compromises between aesthetics, rather than trying to satisfy one or two of them to the fullest. We therefore introduce a new algorithm: BIGANGLE. This algorithm produces drawings with multiple aesthetics being improved at the same time, compared to a classical spring algorithm. A user study comparing these two algorithms indicates that BIGANGLE induces a significantly better task performance and a lower cognitive load, therefore resulting in better graph drawings in terms of human cognitive efficiency.Our study indicates that aesthetics should not be considered separately. Improving multiple aesthetics at the same time, even to small extents, will have a better chance to make resultant drawings more effective. Although this finding is based on a study of algorithms, it also applies in general graph visualization and evaluation. Highlights? We have introduced cosine force, which is to increase the size of crossing angles. ? We have introduced sine force, which is to increase the angular resolution of vertices. ? We have introduced and implemented a force-directed algorithm, which improves multiple aesthetics at the same time. ? We have conducted a human study, which was the first to examine the collective effect of multiple aesthetics on humans. ? We have presented empirical evidence showing that improving multiple aesthetics produces better graph drawings. <s> BIB011 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> Objective: Aesthetics are important in algorithm design and graph evaluation. This paper presents two user studies that were conducted to investigate the impact of crossing angles on human graph comprehension. Method and results: These two studies together demonstrate our newly proposed two-step approach for testing graph aesthetics. The first study is a controlled experiment with purposely-generated graphs. Twenty-two subjects participated in the study and were asked to determine the length of a path which was crossed by a set of parallel edges at different angles. The result of an analysis of variance showed that larger crossing angles induced better task performance. The second study was a non-controlled experiment with general real world graphs. Thirty-seven subjects participated in the study and were asked to find the shortest path of two pre-selected nodes in a set of graph drawings. The results of simple regression tests confirmed the negative effect of small crossing angles. This study also showed that among our four proposed candidates, the minimum crossing angle on the path was the best measure for the aesthetic when path finding is important. Conclusion: Larger crossing angles make graphs easier to read. Implications: In situations where crossings cannot be completely removed (for example, graphs are non-planar, or a drawing convention is applied), or where effort needed to remove all crossings cannot be justified, the crossing angle should be maximized to reduce the negative impact of crossings to the minimum. <s> BIB012 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings. <s> BIB013 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> Partial Edge Drawing (PED) is a popular graph drawing style aimed at reducing edge crossings and visual clutter. PEDs are straight-line drawings where the central part of each edge is erased, and the length of the two remaining segments are computed so as to preserve useful geometric information. Recent studies on this approach focus on symmetric and δ-homogeneous PEDs (δ-SHPEDs). Given a straight-line drawing, a δ-SHPED of this drawing is immediately defined for a fixed value of δ. In particular, some edge crossings may not be avoidable, although the amount of ink removed from the original drawing might be large (e.g., 50% when δ = 1/4). On the other hand, it is possible to maximize the ink and remove edge crossings by renouncing to homogeneity. We present heuristics to produce symmetric PEDs that are either crossing-free or where crossings forming large angles are allowed. We also describe a user study in which PEDs obtained via our heuristics are compared with the standard model 1/4-SHPED. Our results suggest that the benefit of homogeneity overcomes in terms of readability the benefit of fewer crossings and more ink. <s> BIB014 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> 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. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), 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 an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be $$\varOmega (n)$$ Ω(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 in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs. <s> BIB015 </s> A Survey on Graph Drawing Beyond Planarity <s> IMPLEMENTATIONS AND EXPERIMENTS <s> The crossing angle of a straight-line drawing $\Gamma$ of a graph $G=(V, E)$ is the smallest angle between two crossing edges in $\Gamma$. Deciding whether a graph $G$ has a straight-line drawing with a crossing angle of $90^\circ$ is $\mathcal NP$-hard. We propose a simple heuristic to compute a drawing with a large crossing angle. The heuristic greedily selects the best position for a single vertex in a random set of points. The algorithm is accompanied by a speed-up technique to compute the crossing angle of a straight-line drawing. We show the effectiveness of the heuristic in an extensive empirical evaluation. Our heuristic was clearly the winning algorithm (CoffeeVM) in the Graph Drawing Challenge 2017. <s> BIB016
The applied research in graph drawing beyond planarity has been mainly pursued along two directions: (i) Cognitive experiments aimed to better understand the impact of some types of forbidden configurations on the capability of a user to execute visualization-based analysis tasks. (ii) The implementation and experimentation of algorithms to compute beyond-planar graph drawings and the development of visualization systems for real-world application domains. We briefly discuss the contributions in these two directions. Cognitive studies. Early cognitive experiments on beyond-planar graphs estimate the effects of crossing angles on human eye movements and performance through the use of eye-tracking systems BIB003 BIB007 . The results show that sharp angles may trigger extra eye movements, causing delays for path search tasks, whereas crossings have usually little impact on node locating tasks. Subsequent experiments confirm the importance of large angle crossings to execute visualizationbased analysis tasks BIB012 BIB004 , thus motivating and stimulating the rich literature about RAC graphs and related graph families BIB009 . Further studies give some evidence that relevant improvements on graph layout readability derive from finding a good tradeoff between different quality metrics, such as crossing and vertex angles, rather than optimizing only one of them BIB011 . Recall that PEDs aim to reduce edge crossings and visual clutter; the central part of each edge is erased and the length of the two remaining segments are computed to preserve useful geometric information BIB002 . An α-SHPED of a straight-line drawing is immediately defined for a fixed value of α BIB010 . In particular, some edge crossings may not be avoidable, although the amount of ink removed from the original drawing might be large (e.g., 50% when α = 1 4 ). On the other hand, it is possible to maximize the ink and remove edge crossings by using different values of α for different edges. Binucci et al. present a user study in which PEDs obtained via heuristics are compared with the standard model 1 4 -SHPED BIB014 . The results suggest that the benefit of homogeneity overcomes, in terms of readability, the benefit of fewer crossings and more ink. Other experiments on beyond-planar graphs focus on a so-called edge stratification approach to analyze complex visualizations of graphs BIB013 . The approach is based on partitioning the edge set of a drawing into a minimal number of layers, such that the edges in each layer define a drawing with some desired properties related to crossings. For example, one can require that the drawing of each layer is planar, or that its crossing angles are larger than a given constant α, or that it is kplanar for some fixed k. The experiments show that the stratification approach is mainly useful for local tasks such as counting the vertex degrees, while it is less effective for more global tasks such as finding shortest paths between pairs of vertices. The edge stratification algorithms proposed by Di Giacomo et al. are sometimes computationally expensive, especially when the drawing on each layer is required to be k-planar for relatively large values of k; most of these algorithms can be successfully applied to drawings with a few hundred vertices and edges BIB013 . Algorithms and systems. Several papers describe heuristics that attempt to optimize some desired properties for edge crossings, often in combination with classical graph drawing conventions. For example, to improve the readability of circular layouts, the MAXCIR post-processing algorithm BIB005 aims to increase crossing angles by using Quadratic Programming; it is fast in practice and yields better results compared to a traditional equal-spacing algorithm. BIGANGLE BIB011 is a force-directed algorithm that computes drawings of graphs with multiple quality metrics being improved at the same time; these metrics include crossing and vertex angle resolution. Argyriou et al.  propose another force-directed algorithm that computes drawings with high crossing and vertex angle resolution. In a recent paper, Bekos et al.  present a new algorithm to improve the crossing resolution of a drawing and discuss experiments in which this algorithms outperforms the algorithms in other works  BIB011 . A further contribution in the same direction as BIGANGLE is the topology-driven force-directed framework BIB006 . It allows the design of graph drawing algorithms that find good tradeoffs between different metrics, such as number of crossings, crossing angle resolution, geodesic edge tendency, and number of edge bends. This approach combines force-directed techniques with the popular topology-shape-metrics approach, originally proposed to compute bend-minimum orthogonal drawings BIB001 . Examples of drawings computed by topology-driven force-directed algorithms are shown in Figures 9(a)-9(b). As a follow-up of this work, the same authors implement an algorithm that first computes a straight-line drawing with a force-directed technique and then runs a post-processing procedure to improve the crossing angle resolution by representing edges as smoothed curves (see Figure 9 (c)); each curve is monotone in the direction of the straight-line segment connecting its end-points. The algorithm is applied to the simultaneous embedding of suitably defined networks in a system for conceptual Web-site traffic analysis BIB008 . More recently, Demel et al. presented a heuristic to increase the smallest angle between two crossing edges in a given straight-line drawing, together with a speed-up technique to compute the pair of crossing edges with the smallest crossing angle in a straight-line drawing BIB016 . To compute layered drawings of graphs with large-angle crossings (see Section 8), Di Giacomo et al. describe building block heuristics for extracting a maximum 2-layer RAC subgraph of a given bipartite graph  . They study both the setting in which no fixed ordering for the vertices of each partition set is given and the setting in which one of the two sets has a fixed linear ordering. We finally mention the implementation of an algorithm that computes Ortho-Polygon Visibility Representations (OPVRs) of (nonplanar) graphs BIB015 . As explained in Section 7.2, in an OPVR of a graph G, each vertex is represented as an orthogonal polygon and each edge is either a horizontal or a vertical segment. The vertex complexity of an OPVR is the maximum number of reflex angles inside a polygon representing a vertex. Assuming that the graph G comes with a fixed embedding, the algorithm in Di Giacomo et al. BIB015 tests in O (n 2 ) time whether an OPVR of G exists and, if so, it computes in O (n 5 2 log 3 2 n) time an embedding-preserving OPVR of G with minimum vertex complexity. This algorithm has been experimented on a large set of 1-plane graphs, which always admit an OPVR. The results show that, in practice, the computed OPVRs have usually a high percentage (up to 90% in some cases) of vertices drawn with no reflex corners (i.e., as rectangles).