In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex ...polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n - 1) × (n - 1) grid if either G is triconnected or the triconnected component decomposition tree T (G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n × 2n grid if T (G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 grid if T (G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 20n × 16n grid if T (G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of O(n2) size.
Graph drawing beyond planarity is a research area that has received an increasing attention in the last twenty years, driven by the necessity to mitigate the visual complexity inherent in geometric ...representations of non-planar graphs. This research area stems from the study of graph layouts with forbidden crossing configurations, a well-established subject in geometric and topological graph theory. In this context, the contribution of this paper is as follows: 1) We introduce a new hierarchy of graph families, called <inline-formula> <tex-math notation="LaTeX">k^{+} </tex-math></inline-formula>-real face graphs; for any integer <inline-formula> <tex-math notation="LaTeX">k \geq 1 </tex-math></inline-formula>, a graph G is a <inline-formula> <tex-math notation="LaTeX">k^{+} </tex-math></inline-formula>-real face graph if it admits a drawing <inline-formula> <tex-math notation="LaTeX">\Gamma </tex-math></inline-formula> in the plane such that the boundary of each face (formed by vertices, crossings, and edges) contains at least k vertices of G ("<inline-formula> <tex-math notation="LaTeX">k^{+} </tex-math></inline-formula>" stands for k or more); 2) We give tight upper bounds on the edge density of <inline-formula> <tex-math notation="LaTeX">k^{+} </tex-math></inline-formula>-real face graphs, namely we prove that n-vertex <inline-formula> <tex-math notation="LaTeX">1^{+} </tex-math></inline-formula>-real face and <inline-formula> <tex-math notation="LaTeX">2^{+} </tex-math></inline-formula>-real face graphs have at most <inline-formula> <tex-math notation="LaTeX">5n-10 </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">4n-8 </tex-math></inline-formula> edges, respectively. Furthermore, in a constrained scenario in which all vertices must lie on the boundary of the external face, <inline-formula> <tex-math notation="LaTeX">1^{+} </tex-math></inline-formula>-real face and <inline-formula> <tex-math notation="LaTeX">2^{+} </tex-math></inline-formula>-real face graphs have at most <inline-formula> <tex-math notation="LaTeX">3n-6 </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">2.5n-4 </tex-math></inline-formula> edges, respectively; 3) We characterize the complete graphs that admit a <inline-formula> <tex-math notation="LaTeX">k^{+} </tex-math></inline-formula>-real face drawing or an outer <inline-formula> <tex-math notation="LaTeX">k^{+} </tex-math></inline-formula>-real face drawing for any <inline-formula> <tex-math notation="LaTeX">k \geq 1 </tex-math></inline-formula>. We also provide a clear picture for the majority of complete bipartite graphs; and 4) We establish relationships between <inline-formula> <tex-math notation="LaTeX">k^{+} </tex-math></inline-formula>-real face graphs and other prominent beyond-planar graph families; notably, we show that for any <inline-formula> <tex-math notation="LaTeX">k \geq 1 </tex-math></inline-formula>, the class of <inline-formula> <tex-math notation="LaTeX">k^{+} </tex-math></inline-formula>-real face graphs is not included in any family of beyond-planar graphs with hereditary property.
We introduce and study a constrained planarity testing problem, called 1-Fixed Constrained Planarity, and prove that this problem can be solved in quadratic time for biconnected graphs. Our solution ...is based on a novel definition of fixedness that makes it possible to simplify and extend known techniques about Simultaneous PQ-Ordering. We exploit this result to study different versions of the hybrid planarity testing problem. Namely, we show polynomial-time solutions for a variant of NodeTrix Planarity with fixed sides, for PolyLink Planarity, and for Clique Planarity with fixed sides.
In the last years, many areas in science, business, and engineering have experienced an enormous growth in the amount of data that they are required to analyze. In many cases, this analysis relies ...intimately on data visualization and, as a result, graph drawing has emerged as a new field of research. This paper addresses the challenge of drawing hierarchical graphs, which is one of the most widely used drawing standards. We introduce a new mathematical model to automatically represent a graph based on the alignment of long arcs, which we combine with the classic arc crossing minimization objective in hierarchical drawings. We complement our proposal with a heuristic algorithm that can obtain high-quality results in the short computational time required by graph drawing systems. Our algorithm joins two methodologies, tabu search and strategic oscillation (SOS), to perform a fast and effective exploration of the search space. We conduct extensive experimentation that integrates our new mathematical programming formulation and the SOS tabu search that targets large instances. Our statistical analysis confirms the effectiveness of this proposal.
Numerous patterns found in urban phenomena, such as air pollution and human mobility, can be characterized as many directed geospatial networks (geo-networks) that represent spreading processes in ...urban space. These geo-networks can be analyzed from multiple levels, ranging from the macro -level of summarizing all geo-networks, meso -level of comparing or summarizing parts of geo-networks, and micro -level of inspecting individual geo-networks. Most of the existing visualizations cannot support multilevel analysis well. These techniques work by: 1) showing geo-networks separately with multiple maps leads to heavy context switching costs between different maps; 2) summarizing all geo-networks into a single network can lead to the loss of individual information; 3) drawing all geo-networks onto one map might suffer from the visual scalability issue in distinguishing individual geo-networks. In this study, we propose GeoNetverse , a novel visualization technique for analyzing aggregate geo-networks from multiple levels. Inspired by metro maps, GeoNetverse balances the overview and details of the geo-networks by placing the edges shared between geo-networks in a stacked manner. To enhance the visual scalability, GeoNetverse incorporates a level-of-detail rendering, a progressive crossing minimization, and a coloring technique. A set of evaluations was conducted to evaluate GeoNetverse from multiple perspectives.
Graph Layouts by t‐SNE Kruiger, J. F.; Rauber, P. E.; Martins, R. M. ...
Computer graphics forum,
June 2017, Volume:
36, Issue:
3
Journal Article
Peer reviewed
Open access
We propose a new graph layout method based on a modification of the t‐distributed Stochastic Neighbor Embedding (t‐SNE) dimensionality reduction technique. Although t‐SNE is one of the best ...techniques for visualizing high‐dimensional data as 2D scatterplots, t‐SNE has not been used in the context of classical graph layout. We propose a new graph layout method, tsNET, based on representing a graph with a distance matrix, which together with a modified t‐SNE cost function results in desirable layouts. We evaluate our method by a formal comparison with state‐of‐the‐art methods, both visually and via established quality metrics on a comprehensive benchmark, containing real‐world and synthetic graphs. As evidenced by the quality metrics and visual inspection, tsNET produces excellent layouts.
Graph Neural Networks for Graph Drawing Tiezzi, Matteo; Ciravegna, Gabriele; Gori, Marco
IEEE transaction on neural networks and learning systems,
04/2024, Volume:
35, Issue:
4
Journal Article
Open access
Graph drawing techniques have been developed in the last few years with the purpose of producing esthetically pleasing node-link layouts. Recently, the employment of differentiable loss functions has ...paved the road to the massive usage of gradient descent and related optimization algorithms. In this article, we propose a novel framework for the development of Graph Neural Drawers (GNDs), machines that rely on neural computation for constructing efficient and complex maps. GND is Graph Neural Networks (GNNs) whose learning process can be driven by any provided loss function, such as the ones commonly employed in Graph Drawing. Moreover, we prove that this mechanism can be guided by loss functions computed by means of feedforward neural networks, on the basis of supervision hints that express beauty properties, like the minimization of crossing edges. In this context, we show that GNNs can nicely be enriched by positional features to deal also with unlabeled vertexes. We provide a proof-of-concept by constructing a loss function for the edge crossing and provide quantitative and qualitative comparisons among different GNN models working under the proposed framework.
Crossings between non-homotopic edges Pach, János; Tardos, Gábor; Tóth, Géza
Journal of combinatorial theory. Series B,
September 2022, 2022-09-00, Volume:
156
Journal Article
Peer reviewed
Open access
A multigraph drawn in the plane is called non-homotopic if no pair of its edges connecting the same pair of vertices can be continuously transformed into each other without passing through a vertex, ...and no loop can be shrunk to its end-vertex in the same way. Edges are allowed to intersect each other and themselves. It is easy to see that a non-homotopic multigraph on n>1 vertices can have arbitrarily many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph with n vertices and m>4n edges is larger than cm2n for some constant c>0, and that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not asymptotically sharp as n is fixed and m tends to infinity.
With the advent of the era of big data, more and more complex networks and knowledge based systems require data visualization for analysis and presentation, where graphs have become a standard ...representation model. Graph drawing addresses the problems of constructing geometric representations of graphs to make them easy to analyze. In this paper we aim to reduce the edge crossing number in the context of the incremental graph drawing problem (IGDP), in which we want to preserve the layout of a graph over successive drawings to present complex networks or knowledge-based systems. Specifically, we propose a metaheuristic algorithm called multiple neighborhood solution-based tabu search (MNSB-TS) by combining a solution-based tabu strategy and a multiple neighborhood structure for solving the incremental graph drawing problem. Our MNSB-TS approach introduces four neighborhood operators to accompany the solution-based tabu strategy for determining the tabu status of each neighbor solution. Extensive computational experiments on public benchmark instances demonstrate that the proposed MNSB-TS is highly competitive in comparison with the state-of-the-art heuristics and the exact optimization solver Gurobi. Key components of the approach are analyzed to evaluate their impact on algorithm performance and learn which search mechanisms are better suited for incremental graph drawing.
•A novel method combines a solution-based tabu search and multiple neighborhood search.•The corresponding fast neighborhood evaluation methods for intensification.•A dynamic diversification phase which varies the diversification intensity.•The conducted experiments show the efficiency of the proposed algorithm.
•There are knight's tours in n×n boards with less than 9.25n turns and 12n crossings.•Any knight's tour in an n×n board has over 5.99n turns and 4n crossings.•Using a 2×2 formation of parallel knight ...moves helps reduce both turns and crossings.•A new knight's tour algorithm minimizes turns and crossings simultaneously.•Our new knight's tour algorithm can be generalized to 3D boards and similar pieces.
We introduce two new metrics of “simplicity” for knight's tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.25n+O(1) turns and 12n+O(1) crossings on an n×n board, and we show lower bounds of (6−ϵ)n and 4n−O(1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 9.25/6+o(1) and 3+o(1). Our algorithm takes linear time and is fully parallelizable, i.e., the tour can be computed in O(n2/p) time using p processors in the CREW PRAM model. We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1,4)-leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases.
PDF
