A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <s> A study of questions raised by the conception of a tool for computer-aided decision analysis that would facilitate interactive structural systems analysis and the tool itself, named GT1VX, are presented. Focusing on systems known by their elements and the relations among them, two hierarchies that apply to graphs of different types: first, rank hierarchy that is adapted to digraphs with cycles and second, number hierarchy that applies to strongly connected digraphs and to nondirected graphs are presented. Standard forms of representation of these hierarchies are defined, and the question of reducing the number of edge crossings in the drawings is studied. Finally, the software GT1VX is described. It was developed for the automatic display of graphs hierarchized according to the rank hierarchy and to the number hierarchy; GT1VX yields, within agreeable computing times, drawings in the standard forms of representation that have a limited number of edge crossings. Three real-life examples of the application of this tool are also presented. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <s> Two kinds of new methods are developed to obtain effective representations of hierarchies automatically: theoretical and heuristic methods. The methods determine the positions of vertices in two steps. First the order of the vertices in each level is determined to reduce the number of crossings of edges. Then horizontal positions of the vertices are determined to improve further the readability of drawings. The theoretical methods are useful in recognizing the nature of the problem, and the heuristic methods make it possible to enlarge the size of hierarchies with which we can deal. Performance tests of the heuristic methods and several applications are presented. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <s> A layout algorithm is presented that allows the automatic drawing of data flow diagrams, a diagrammatic representation widely used in the functional analysis of information systems. A grid standard is defined for such diagrams, and aesthetics for good readability are identified. The layout algorithm receives as input an abstract graph specifying connectivity relations between the elements of the diagram, and produces as output a corresponding diagram according to the aesthetics. The basic strategy is to build incrementally the layout; first, a good topology is constructed with few crossings between edges; subsequently, the shape of the diagram is determined in terms of angles appearing along edges. and finally dimensions are given to the graph, obtaining a grid skeleton for the diagram. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <s> A common method for drawing directed graphs is, as a first step, to partition the vertices into a set of k levels and then, as a second step, to permute the vertices within the levels such that the number of crossings is minimized. We suggest an alternative method for the second step, namely, removing the minimal number of edges such that the resulting graph is k-level planar. For the final diagram the removed edges are reinserted into a k-level planar drawing. Hence, instead of considering the k-level crossing minimization problem, we suggest solving the k-level planarization problem. In this paper we address the case k=2. First, we give a motivation for our approach. Then, we address the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is NP-hard. Based on a characterization of 2-level planar graphs, we give an integer linear programming formulation for the 2-level planarization problem. Moreover, we define and investigate the polytope \(2\mathcal{L}\mathcal{P}\mathcal{S}\)(G) associated with the set of all 2-level planar subgraphs of a given 2-level graph G. We will see that this polytope has full dimension and that the inequalities occuring in the integer linear description are facet-defining for \(2\mathcal{L}\mathcal{P}\mathcal{S}\)(G). The inequalities in the integer linear programming formulation can be separated in polynomial time, hence they can be used efficiently in a cutting plane method for solving practical instances of the 2-level planarization problem. Furthermore, we derive new inequalities that substantially improve the quality of the obtained solution. We report on first computational results. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <s> Abstract Information visualisation systems which generate diagrams representing discrete relational information must consider potential users if they are to be effective. Many algorithms which render an abstract graph structure as a diagram are valued for their conformance to aesthetic criteria (e.g. reducing the number of edge crossings, maximising symmetry), or for computational efficiency. They are not usually judged on their ability to produce diagrams that maximise human performance. This paper presents the results of experiments investigating the relative worth (from an HCI point of view) of graph drawing aesthetics and algorithms using a single graph. The results indicate that while some individual aesthetics affect human performance, it is difficult to say that one algorithm is ‘better’ than another from a relational understanding point of view. Designers of automatic layout algorithms, and the systems which embody such algorithms, can benefit from this study and this human-centred approach, by adapting their methods to focus on user concerns, rather than computational ones. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <s> A large class of diagrams can be informally characterized as node-link diagrams. Typically nodes represent entities, and links represent relationships between them. The discipline of graph drawing is concerned with methods for drawing abstract versions of such diagrams. At the foundation of the discipline are a set of graph aesthetics (rules for graph layout) that, it is assumed, will produce graphs that can be clearly understood. Examples of aesthetics include minimizing edge crossings and minimizing the sum of the lengths of the edges. However, with a few notable exceptions, these aesthetics are taken as axiomatic, and have not been empirically tested. We argue that human pattern perception can tell us much that is relevant to the study of graph aesthetics including providing a more detailed understanding of aesthetics and suggesting new ones. In particular, we find the importance of good continuity (ie keeping multi-edge paths as straight as possible) has been neglected. We introduce a methodology for evaluating the cognitive cost of graph aesthetics and we apply it to the task of finding the shortest paths in spring layout graphs. The results suggest that after the length of the path the two most important factors are continuity and edge crossings, and we provide cognitive cost estimates for these parameters. Another important factor is the number of branches emanating from nodes on the path. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <s> Many automatic graph layout algorithms have been designed and implemented to display relational data in a graphical (usually node-arc) manner. The success of these algorithms is typically measured by their computational efficiency and the extent to which they conform to aesthetic criteria (for example, minimising the number of crossings, maximising symmetry). Little research has been performed on the usability aspects of such algorithms: do they produce graph drawings that make the embodied information easy to use and understandq Is the computational effort expended on conforming to the assumed aesthetic criteria justifiable with respect to better usabilityq This paper reports on usability studies that were performed to investigate the merit of automatic graph layout algorithms with respect to human use. The paper describes three ways in which this issue has been considered experimentally: first, investigating individual aesthetic criteria in simple, abstract graph structures; second, investigating the results of common automatic graph layout algorithms; and third, investigating individual aesthetic criteria and other relevant secondary notations in Unified Modeling Language class and collaboration diagrams. The results show that the use of only some aesthetics affect usability significantly, and that the semantic domain of the graph drawings affects which aesthetic criteria need to be emphasised. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <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> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <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> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> INTRODUCTION <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> BIB010
In the mid-1980s, the early pioneers of graph drawing had the intuition that a drawing with too many edge crossings is harder to read than a drawing of the same graph with fewer edge crossings (see, e.g.,  BIB003 BIB001 BIB002 ). This intuition was later confirmed by a series of cognitive experimental studies (see, e.g., BIB005 BIB007 BIB006 ). As a result, a large part of the existing literature on graph drawing showcases elegant algorithms and sophisticated data structures under the assumption that the input graph is planar (i.e., it admits a drawing without edge crossings). When the input graph is nonplanar, crossing minimization heuristics are used to insert a small number of dummy vertices corresponding to the edge crossings to obtain a planarization of the input graph. A crossing-free drawing of the planarization can be computed using one of the algorithms for planar graphs, and then the crossings are reinserted by removing the dummy vertices. This approach is commonly adopted and works well for graphs of relatively small size, up to a few hundred vertices and edges (see, e.g.,   ). However, the technological advances of the past 20 years have generated torrents of relational data that are typically modeled as large graphs with thousands of vertices (or more). These graphs are often hard to visually analyze due, mainly, to their large size, which typically implies that a high number of edge crossings is unavoidable even by the most sophisticated planarization approaches. As a consequence, a strong consensus has developed that a new theory of nonplanar graph drawing is needed. In this context, in the early 2000s, Mutzel ran an informal experiment with computer scientists at a Dagstuhl workshop where she presented two different drawings of the same bipartite graph: One has the minimum number of edge crossings, the second has 41% more edge crossings, but it has a skewness of four, which means that all crossings can be removed by deleting four edges in the drawing. All computer scientists found the drawing with skewness four more readable than the one with fewer edge crossings. This is reported BIB004 as anecdotal evidence that the topological properties of the edge crossings may be more important than their number. Besides the topological properties of the edge crossings, the impact of their geometric properties on the readability of a nonplanar drawing was evaluated in a pioneering sequence of user experiments performed in the graph drawing research lab at the University of Sydney. By means of an eye-tracking device, the experiments present statistical evidence that crossings significantly affect human understanding if they form acute angles, but if these angles vary in the range from about π 3 to π 2 they guarantee good readability properties BIB008 BIB010 BIB009 . These empirical experiences suggest that a new theory of nonplanar graph drawing can be developed under the assumption that not only the number of edge crossings but also their (topological and/or geometric) properties have an impact on the readability of a diagram. Hence, a natural step toward understanding nonplanar representations of graphs is to classify and study them in terms of forbidden crossing configurations. This is, in a broad sense, the aim and scope of the rapidly growing research area of graph drawing beyond planarity  . Table 1 reports some examples of beyond-planar graphs with a description of their forbidden crossing configurations 2 . Overview and paper organization. The goal of this survey is to classify and describe prominent results and promising research directions in the fertile area of graph drawing beyond planarity. The survey addresses the following questions. Q1 What are the forbidden crossing configurations and the main research directions that have been studied so far? Q2 For each such direction, what are the main combinatorial results, and which algorithms have been designed, implemented, and experimentally evaluated? Q3 What are the most relevant open problems and the least explored research directions in this area? To answer Question Q1, in Section 3 we define graph families that avoid forbidden crossing configurations, and we present a taxonomy of the main research directions in graph drawing beyond planarity. Sections 4-9 address Question Q2, using the taxonomy as a guideline to classify the main combinatorial and algorithmic results. At the end of each section, we address Question Q3 by discussing some relevant open problems. Basic definitions on graph drawing can be found in Section 2. A Survey on Graph Drawing Beyond Planarity 4:3 terminology, we make no distinction between the vertices and edges of a graph and the points and arcs representing them, respectively. Two edges of Γ cross if they have a point in common distinct from their endpoints; this point is a crossing. We assume that an edge does not contain a vertex other than its endpoints, no two edges meet tangentially, and no three edges share a crossing. Γ is simple if any two edges intersect in at most one point, which is either a common endpoint or an interior point where the two edges properly cross. Thus, in a simple drawing, two adjacent edges do not cross and two nonadjacent edges cross at most once. A drawing Γ of G divides the plane into topologically connected regions, called faces, separated by edges or fragments of edges. The infinite region is called the external face; the other regions are the internal faces. Note that the boundary of a face may contain both vertices of the graph and crossings. An embedding of G is an equivalence class of drawings of G under homeomorphism of the plane (i.e., is a class of drawings of G that define the same set of [external and internal] faces). A graph with a fixed embedding is called an embedded graph. A drawing without crossings is planar. A graph is planar if it admits a planar drawing. A planar embedding is the embedding of a planar drawing. A graph with a fixed planar embedding is an embedded planar graph, or, briefly, a plane graph. An embedding of a graph G defines, for each vertex v and for each crossing c, the clockwise order of the edges incident to v and to c. A rotation system of G is a relaxation of an embedding of G in which the clockwise order of the edges is fixed only for each vertex, while no information is given about which pairs of edges cross or their order of intersection. If G is planar, a planar embedding of G corresponds to a rotation system plus the choice of the external face (see Figure 1 ). In a polyline drawing of a graph, each edge is a chain of segments; a bend is a point where two segments of the same edge meet. A k-bend drawing is a polyline drawing with at most k bends per edge. A 0-bend drawing is also called a straight-line drawing. We remark that, in the literature, a drawing of a graph is sometimes called a topological graph and a straight-line drawing is sometimes called a geometric graph (see, e.g., Chapter 10 in  ). In the remainder of this article, we use the pair of terms "drawing" and "topological graph" and the pair "straight-line drawing" and "geometric graph" interchangeably.