A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> In this paper we consider a problem related to questions of optimal circuit layout: Given a graph or network, how can we embed it in a planar surface so as to minimize the number of edge-crossings? We show that this problem is NP-complete, and hence there is not likely to be any efficient way to design an optimal embedding. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> We propose a planarization algorithm for clustered graphs and experimentally test its efficiency and effectiveness. Further, we integrate our planarization strategy into a complete topology-shape-metrics algorithm for drawing clustered graphs in the orthogonal drawing convention. <s> BIB002 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of graphs from the mixed style drawings. The basic idea is to cover a layered graph by complete bipartite subgraphs (bicliques), then replace bicliques with tree-like structures. The biclique cover problem is reduced to a special edge coloring problem and solved by heuristic coloring algorithms. Our method can be extended to obtain multi-depth confluent layered drawings. <s> BIB003 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> A compound graph is a frequently encountered type of data set. Relations are given between items, and a hierarchy is defined on the items as well. We present a new method for visualizing such compound graphs. Our approach is based on visually bundling the adjacency edges, i.e., non-hierarchical edges, together. We realize this as follows. We assume that the hierarchy is shown via a standard tree visualization method. Next, we bend each adjacency edge, modeled as a B-spline curve, toward the polyline defined by the path via the inclusion edges from one node to another. This hierarchical bundling reduces visual clutter and also visualizes implicit adjacency edges between parent nodes that are the result of explicit adjacency edges between their respective child nodes. Furthermore, hierarchical edge bundling is a generic method which can be used in conjunction with existing tree visualization techniques. We illustrate our technique by providing example visualizations and discuss the results based on an informal evaluation provided by potential users of such visualizations <s> BIB004 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> Visualization of clustered graphs has been a research area since many years. In this paper, we describe a new approach that can be used in real application where graph does not contain only topological information but also extrinsic parameters (i.e. user attributes on edges and nodes). In the case of force-directed algorithm, management of attributes corresponds to take into account edge weights. We propose an extension of the GRIP algorithm in order to manage edge weights. Furthermore, by using Voronoi diagram we constrained that algorithm to draw each cluster in a non overlapping convex region. Using these two extensions we obtained an algorithm that draw clustered weighted graphs. Experimentation has been done on data coming from biology where the network is the genes- proteins interaction graph and where the attributes are gene expression values from microarray experiments. <s> BIB005 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> The need to visualize large social networks is growing as hardware capabilities make analyzing large networks feasible and many new data sets become available. Unfortunately, the visualizations in existing systems do not satisfactorily resolve the basic dilemma of being readable both for the global structure of the network and also for detailed analysis of local communities. To address this problem, we present NodeTrix, a hybrid representation for networks that combines the advantages of two traditional representations: node-link diagrams are used to show the global structure of a network, while arbitrary portions of the network can be shown as adjacency matrices to better support the analysis of communities. A key contribution is a set of interaction techniques. These allow analysts to create a NodeTrix visualization by dragging selections to and from node-link and matrix forms, and to flexibly manipulate the NodeTrix representation to explore the dataset and create meaningful summary visualizations of their findings. Finally, we present a case study applying NodeTrix to the analysis of the InfoVis 2004 coauthorship dataset to illustrate the capabilities of NodeTrix as both an exploration tool and an effective means of communicating results. <s> BIB006 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> We present an algorithm for the layout of undirected compound graphs, relaxing restrictions of previously known algorithms in regards to topology and geometry. The algorithm is based on the traditional force-directed layout scheme with extensions to handle multi-level nesting, edges between nodes of arbitrary nesting levels, varying node sizes, and other possible application-specific constraints. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory. The algorithm has also been successfully implemented as part of a pathway integration and analysis toolkit named PATIKA, for drawing complicated biological pathways with compartmental constraints and arbitrary nesting relations to represent molecular complexes and various types of pathway abstractions. <s> BIB007 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> Graphs depicted as node-link diagrams are widely used to show relationships between entities. However, nodelink diagrams comprised of a large number of nodes and edges often suffer from visual clutter. The use of edge bundling remedies this and reveals high-level edge patterns. Previous methods require the graph to contain a hierarchy for this, or they construct a control mesh to guide the edge bundling process, which often results in bundles that show considerable variation in curvature along the overall bundle direction. We present a new edge bundling method that uses a self-organizing approach to bundling in which edges are modeled as flexible springs that can attract each other. In contrast to previous methods, no hierarchy is used and no control mesh. The resulting bundled graphs show significant clutter reduction and clearly visible high-level edge patterns. Curvature variation is furthermore minimized, resulting in smooth bundles that are easy to follow. Finally, we present a rendering technique that can be used to emphasize the bundling. <s> BIB008 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> Many different approaches have been proposed for the challenging problem of visually analyzing large networks. Clustering is one of the most promising. In this paper we propose a new goal for clustering that is especially tailored to hybrid-visualization tools. Namely, that of producing both intra-cluster graphs and inter-cluster graph that are suitable for highly-readable visualizations within different representation conventions. We formalize this concept in the (X,Y)-clustering framework, where Y is the class that defines the desired topological properties of intra-cluster graphs and X is the class that defines the desired topological properties of the inter-cluster graph. By exploiting this approach hybrid-visualization tools can effectively combine different node-link and matrix-based representations, allowing the users to interactively explore the graph by expansion/contraction of clusters without loosing their mental map. As a proof of concept, we describe the system VHYXY (Visual Hybrid (X,Y)-clustering) that integrates our techniques and we present the results of case studies to the visual analysis of co-authorship networks. <s> BIB009 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> A 2-layer drawing represents a bipartite graph where each vertex is a point on one of two parallel lines, no two vertices on the same line are adjacent, and the edges are straight-line segments. In this paper we study 2-layer drawings where any two crossing edges meet at right angle. We characterize the graphs that admit this type of drawing, provide linear-time testing and embedding algorithms, and present a polynomial-time crossing minimization technique. Also, for a given graph G and a constant k, we prove that it is \(\mathcal{NP}\)-complete to decide whether G contains a subgraph of at least k edges having a 2-layer drawing with right angle crossings. <s> BIB010 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> In a drawing of a clustered graph vertices and edges are drawn as points and curves, respectively, while clusters are represented by simple closed regions. A drawing of a clustered graph is c-planar if it has no edge-edge, edge-region, or region-region crossings. Determining the complexity of testing whether a clustered graph admits a c-planar drawing is a long-standing open problem in the Graph Drawing research area. An obvious necessary condition for c-planarity is the planarity of the graph underlying the clustered graph. However, such a condition is not sufficient and the consequences on the problem due to the requirement of not having edge-region and region-region crossings are not yet fully understood. In order to shed light on the c-planarity problem, we consider a relaxed version of it, where some kinds of crossings (either edge-edge, edge-region, or region-region) are allowed even if the underlying graph is planar. We investigate the relationships among the minimum number of edge-edge, edge-region, and region-region crossings for drawings of the same clustered graph. Also, we consider drawings in which only crossings of one kind are admitted. In this setting, we prove that drawings with only edge-edge or with only edge-region crossings always exist, while drawings with only region-region crossings may not. Further, we provide upper and lower bounds for the number of such crossings. Finally, we give a polynomial-time algorithm to test whether a drawing with only region-region crossings exist for biconnected graphs, hence identifying a first non-trivial necessary condition for c-planarity that can be tested in polynomial time for a noticeable class of graphs. <s> BIB011 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> The crossing number is a popular tool in graph drawing and visualization, but there is not really just one crossing number; there is a large family of crossing number notions of which the crossing number is the best known. We survey the rich variety of crossing number variants that have been introduced in the literature for purposes that range from studying the theoretical underpinnings of the crossing number to crossing minimization for visualization problems. <s> BIB012 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> The edge, which can encode relational data in graphs and multidimensional data in parallel coordinates plots, is an important visual primitive for encoding data in information visualization research. However, when data become very large, visualizations often suffer from visual clutter as thousands of edges can easily overwhelm the display and obscure underlying patterns. Many edge-bundling techniques have been proposed to reduce visual clutter in visualizations. In this survey, we briefly introduce the visual-clutter problem in visualizations. Thereafter, we review the cost-based, geometry-based, and image-based edge-bundling methods for graphs, parallel coordinates, and flow maps. We then describe the various visualization applications that use edge-bundling techniques and discuss the evaluation studies concerning the effectiveness of edge-bundling methods. An edge-bundling taxonomy is proposed at the end of this survey. <s> BIB013 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> The visual analysis of large and complex relational data sets is a growing need in many application domains, such as social sciences, biology, computer networks, and software engineering. In this respect, the capability of quickly computing two-dimensional layouts of hierarchically clustered networks plays an important role and should be a major requirement of many graph visualization systems. We present algorithmic and experimental advances on the subject, namely: (i) we propose a new drawing algorithm that combines space-filling and fast force-directed methods; it runs in O(n logn+m) time, where n and m are the number of vertices and edges of the network, respectively. This running time does not depend on the number of clusters, thus the algorithm guarantees good time performance independently of the structure of the cluster hierarchy. As a further advantage, the algorithm can be easily parallelized. (ii) We discuss the results of an experimental analysis aimed at understanding which clustering algorithms can be used in combination with our visualization technique to generate better quality drawings for small-world and scale-free networks of medium and large size. As far as we know, no previous similar experiments have been done to this aim. <s> BIB014 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> 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. <s> BIB015 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call \(h\) -Clique2Path Planarity: Given a graph G, whose vertices are partitioned into subsets of size at most h, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of G is planar. We study this problem when G is a simple topological graph, and establish its complexity in relation to k-planarity. We prove that \(h\) -Clique2Path Planarity is NP-complete even when \(h=4\) and G is a simple 3-plane graph, while it can be solved in linear time, for any h, when G is 1-plane. <s> BIB016 </s> A Survey on Graph Drawing Beyond Planarity <s> CONCLUSION <s> We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant k. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be chosen arbitrarily. We show that NodeTrix planarity testing with fixed sides can be solved in O(k3k+32·n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(k^{3k+\frac{3}{2}} \cdot n)$$\end{document} time for every flat clustered graph that can be reduced to a partial 2-tree by collapsing its clusters into single vertices. In the general case, NodeTrix planarity testing with fixed sides can be solved in O(n) time for k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 2$$\end{document}, but it is NP-complete for any k>2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k > 2$$\end{document}. NodeTrix planarity testing remains NP-complete also in the free sides model when k>4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k > 4$$\end{document}. <s> BIB017
The treatment of edge crossings in graph visualization embraces other topics that have not been discussed in the previous sections. Although these topics are not properly recognized as part of the literature on graph drawing beyond planarity, recent works have established connections with beyond-planar graph families, which highlight new and interesting research directions. Crossing minimization. Computing drawings of graphs with a minimum number of crossings, as well as determining the crossing number of a graph, are problems with a long tradition (see, e.g.,  BIB012 for surveys on the subject). It is well known that the crossing minimization problem is NP-complete, and it remains hard also in very restricted scenarios (for instance, when the graph is bipartite and we look for a straight-line 2-layer drawing of it BIB001 ). However, for 2-layer RAC drawable graphs, the problem can be solved efficiently BIB010 , which suggests that the crossing minimization problem might be polynomial-time solvable also with respect to other forbidden crossing configurations. Relaxed clustered planarity. In a clustered graph G, vertices are grouped into (hierarchical) clusters. In a drawing of G, each cluster should be represented as a closed region containing all (and only) its vertices and all (and only) its subclusters. Also, an edge should not traverse a cluster if both its end vertices are outside it. Many papers study how to efficiently test whether a clustered planar graph admits a crossing-free drawing that meets the aforementioned properties   , and practical drawing heuristics have also been conceived, even for nonplanar large graphs BIB005 BIB002 BIB014 BIB007 . In the context of graph drawing beyond planarity, relaxed models of clustered planarity may disallow only some types of crossings. See Angelini et al. BIB011 for initial steps in this direction. Hybrid visualizations. The use of matrix-based representations combined with the classical node-link representation has been proposed to diminish the negative effect of visual clutter in large and locally dense networks BIB009 BIB006 . More recently, the planarity testing and embedding problem of this type of hybrid visualizations have been further formalized BIB015 BIB017 , and new families of beyond-planar graphs related to hybrid visualizations have been defined BIB016  . Edge bundling. The idea of grouping edges to get planar drawings of nonplanar graphs was originally proposed under the name of confluent drawings  BIB003 . Later, practical edge-bundling techniques were used to cope with the visual clutter problem in node-link diagrams of large and dense graphs BIB004 BIB008 BIB013 . The idea is that "similar" edges are deformed and grouped into bundles, thus providing a more abstract and uncluttered view of the original drawing at the expense of possible ambiguities in terms of connections between vertices. Very recently, the use of edge bundling has been proposed in the context of graph drawing beyond planarity, with the introduction of the family of 1-fan-bundle planar graphs, which combines edge bundling with fan-planar graphs  . Following this example, other families can be conceived and studied.