A Survey on Graph Drawing Beyond Planarity <s> Graph Families <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> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Graph Families <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> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> Graph Families <s> A graph G is an a-angle crossing (aAC) graph if every pair of crossing edges in G intersect at an angle of at least a. The concept of right angle crossing (RAC) graphs (a=Pi/2) was recently introduced by Didimo et. al. It was shown that any RAC graph with n vertices has at most 4n-10 edges and that there are infinitely many values of n for which there exists a RAC graph with n vertices and 4n-10 edges. In this paper, we give upper and lower bounds for the number of edges in aAC graphs for all 0 < a < Pi/2. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> Graph Families <s> We consider graphs that admit polyline drawings where all crossings occur at the same angle α ∈ (0, π/2). We prove that every graph on n vertices that admits such a polyline drawing with at most two bends per edge has O(n) edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest. <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> Graph Families <s> In this paper we study non-planar drawings of graphs, and study trade-offs between the crossing resolution (i.e., the minimum angle formed by two crossing segments), the curve complexity (i.e., maximum number of bends per edge), the total number of bends, and the area. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> Graph Families <s> We consider graphs that admit polyline drawings where all crossings occur at the same angle $\alpha\in (0,\frac{\pi}{2}]$. We prove that every graph on $n$ vertices that admits such a polyline drawing with at most two bends per edge has $O(n)$ edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> Graph Families <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> BIB007
The beyond-planar graph families considered in this survey are defined as graphs that admit drawings without specific forbidden configurations (i.e., sets of edges that violate some desired topological or geometric property of the edge crossings). Table 1 provides a schematic illustration of some beyond-planar graph families, among the most studied. For each family X , we define what a drawing of type X is. A graph belongs to family X if it admits a drawing of type X . Definitions based on first-order logic formulas have been recently proposed for many of these types of drawings  . in Didimo et al.  , motivated by cognitive studies that suggest a positive correlation between large crossing angles and human understanding of graph visualizations BIB001 BIB007 BIB002 , and by the common use of large angle crossings in handmade real-world diagrams, such as metro maps   . RAC drawings with edge bends are also studied in the literature and will be discussed in this survey. ACEα and ACLα drawings. ACEα and ACLα drawings are natural variants of RAC drawings that are parametric in a value α ∈ (0, π 2 ). In a straight-line ACEα drawing, any two crossing edges form an angle equal to α. Graphs that admit this type of drawing were originally introduced with the name of αAC = graphs BIB004 BIB006 . In a straight-line ACLα drawing, the value of any crossing angle is at least α. These drawings were independently introduced by two different works; in Di Giacomo et al. BIB005 they are called LAC α drawings, and in Dujmovic et al. BIB003 they are called αAC drawings. As for RAC drawings, ACEα and ACLα drawings with edge bends are also considered in this survey.