Graph Drawing Beyond Planarity is a rapidly growing research area that classifies and studies geometric representations of nonplanar graphs in terms of forbidden crossing configurations. The aim of ...this survey is to describe the main research directions in this area, the most prominent known results, and some of the most challenging open problems.
We describe the University of Florida Sparse Matrix Collection, a large and actively growing set of sparse matrices that arise in real applications. The Collection is widely used by the numerical ...linear algebra community for the development and performance evaluation of sparse matrix algorithms. It allows for robust and repeatable experiments: robust because performance results with artificially generated matrices can be misleading, and repeatable because matrices are curated and made publicly available in many formats. Its matrices cover a wide spectrum of domains, include those arising from problems with underlying 2D or 3D geometry (as structural engineering, computational fluid dynamics, model reduction, electromagnetics, semiconductor devices, thermodynamics, materials, acoustics, computer graphics/vision, robotics/kinematics, and other discretizations) and those that typically do not have such geometry (optimization, circuit simulation, economic and financial modeling, theoretical and quantum chemistry, chemical process simulation, mathematics and statistics, power networks, and other networks and graphs). We provide software for accessing and managing the Collection, from MATLAB™, Mathematica™, Fortran, and C, as well as an online search capability. Graph visualization of the matrices is provided, and a new multilevel coarsening scheme is proposed to facilitate this task.
Due to an editorial oversight, a flaw in the proof (not the result) of Lemma 5 remained in the TCS published version of the following paper “On the edge-length ratio of outerplanar graphs”, published ...in Theoretical Computer Science, vol. 770, pp. 88–94, 2019. Please refer to the electronic version on HAL (https://hal.inria.fr/hal-01886947) for the correct version.
In this paper, we present new quality metrics for symmetric graph drawing based on group theory. Roughly speaking, the new metrics are faithfulness metrics, i.e., they measure how faithfully a ...drawing of a graph displays the ground truth (i.e., geometric automorphisms) of the graph as symmetries. More specifically, we introduce two types of automorphism faithfulness metrics for displaying: (1) a single geometric automorphism as a symmetry ( axial or rotational ), and (2) a group of geometric automorphisms ( cyclic or dihedral ). We present algorithms to compute the automorphism faithfulness metrics in <inline-formula><tex-math notation="LaTeX">O(n \log n)</tex-math></inline-formula> time. Moreover, we also present efficient algorithms to detect exact symmetries in a graph drawing. We then validate our automorphism faithfulness metrics using deformation experiments. Finally, we use the metrics to evaluate existing graph drawing algorithms to compare how faithfully they display geometric automorphisms of a graph as symmetries.
Visually encoding quantitative information associated with graph links is an important problem in graph visualization. A conventional approach is to vary the thickness of lines to encode the strength ...of connections in node-link diagrams. In this paper, we present Sticky Links , a novel visual encoding method that draws graph links with stickiness . Taking the metaphor of links with glues, sticky links represent connection strength using spiky shapes, ranging from two broken spikes for weak connections to connected lines for strong connections. We conducted a controlled user study to compare the efficiency and aesthetic appeal of stickiness with conventional thickness encoding. Our results show that stickiness enables more effective and expressive quantitative encoding while maintaining the perception of node connectivity. Participants also found sticky links to be more aesthetic and less visually cluttering than conventional thickness encoding. Overall, our findings suggest that sticky links offer a promising alternative to conventional methods for encoding quantitative information in graphs.
Graph drawing readability metrics are routinely used to assess and create node-link layouts of network data. Existing readability metrics fall short in three ways. The many count-based metrics such ...as edge-edge or node-edge crossings simply provide integer counts, missing the opportunity to quantify the amount of overlap between items, which may vary in size, at a more fine-grained level. Current metrics focus solely on single-level topological structure, ignoring the possibility of multi-level structure such as large and thus highly salient metanodes. Most current metrics focus on the measurement of clutter in the form of crossings and overlaps, and do not take into account the trade-off between the clutter and the information sparsity of the drawing, which we refer to as sprawl. We propose an area-aware approach to clutter metrics that tracks the extent of geometric overlaps between node-node, node-edge, and edge-edge pairs in detail. It handles variable-size nodes and explicitly treats metanodes and leaf nodes uniformly. We call the combination of a sprawl metric and an area-aware clutter metric a sprawlter metric. We present an instantiation of the sprawlter metrics featuring a formal and thorough discussion of the crucial component, the penalty mapping function. We implement and validate our proposed metrics with extensive computational analysis of graph layouts, considering four layout algorithms and 56 layouts encompassing both real-world data and synthetic examples illustrating specific configurations of interest.
Recent works in graph visualization attempt to reduce the runtime of repulsion force computation of force-directed algorithms using sampling. However, they fail to reduce the runtime for attraction ...force computation to sublinear in the number of edges. We present the SubLinearForce framework for a fully sublinear-time force computation algorithm for drawing large complex graphs. More precisely, we present new sublinear-time algorithms for the attraction force computation of force-directed algorithms. We then integrate them with sublinear-time repulsion force computation to give a fully sublinear-time force computation. Extensive experiments show that our algorithms compute layouts on average 80% faster than the existing linear-time force computation algorithm, while obtaining significantly better quality metrics such as edge crossing and shape-based metrics.
Automatic Drawing of Complex Metro Maps ONDA, Masahiro; MORIGUCHI, Masaki; IMAI, Keiko
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
2021
Journal Article
Peer reviewed
The Tokyo subway is one of the most complex subway networks in the world and it is difficult to compute a visually readable metro map using existing layout methods. In this paper, we present a new ...method that can generate complex metro maps such as the Tokyo subway network. Our method consists of two phases. The first phase generates rough metro maps. It decomposes the metro networks into smaller subgraphs and partially generates rough metro maps. In the second phase, we use a local search technique to improve the aesthetic quality of the rough metro maps. The experimental results including the Tokyo metro map are shown.
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 20n × 16n 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 10n × 5n grid if T (G) has exactly five leaves. We also present a linear-time algorithm to find such a drawing.
PDF
