While a multitude of studies have been conducted on graph drawing, many existing methods only focus on optimizing a single aesthetic aspect of graph layouts, which can lead to sub-optimal results. ...There are a few existing methods that have attempted to develop a flexible solution for optimizing different aesthetic aspects measured by different aesthetic criteria. Furthermore, thanks to the significant advance in deep learning techniques, several deep learning-based layout methods were proposed recently. These methods have demonstrated the advantages of deep learning approaches for graph drawing. However, none of these existing methods can be directly applied to optimizing non-differentiable criteria without special accommodation. In this work, we propose a novel Generative Adversarial Network (GAN) based deep learning framework for graph drawing, called SmartGD, which can optimize different quantitative aesthetic goals, regardless of their differentiability. To demonstrate the effectiveness and efficiency of SmartGD, we conducted experiments on minimizing stress, minimizing edge crossing, maximizing crossing angle, maximizing shape-based metrics, and a combination of multiple aesthetics. Compared with several popular graph drawing algorithms, the experimental results show that SmartGD achieves good performance both quantitatively and qualitatively.
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.
Over the past few decades, a large number of graph layout techniques have been proposed for visualizing graphs from various domains. In this paper, we present a general framework, Taurus, for ...unifying popular techniques such as the spring-electrical model, stress model, and maxent-stress model. It is based on a unified force representation, which formulates most existing techniques as a combination of quotient-based forces that combine power functions of graph-theoretical and Euclidean distances. This representation enables us to compare the strengths and weaknesses of existing techniques, while facilitating the development of new methods. Based on this, we propose a new balanced stress model (BSM) that is able to layout graphs in superior quality. In addition, we introduce a universal augmented stochastic gradient descent (SGD) optimizer that efficiently finds proper solutions for all layout techniques. To demonstrate the power of our framework, we conduct a comprehensive evaluation of existing techniques on a large number of synthetic and real graphs. We release an open-source package, which facilitates easy comparison of different graph layout methods for any graph input as well as effectively creating customized graph layout techniques.
The aim of the study is to examine the graphing skills of prospective elementary mathematics teachers for a socioscientific problem situation related to Covid-19. The research is a qualitative ...research and was carried out with the case study method.The participants consisted of 43 prospective elementary mathematics teachers studying in the third year of a state university in Turkey. Typical case sampling, one of the purposive sampling methods, was used to determine the participants. In the research, an open-ended question that requires drawing three graphs with vital aspects based on a socio-scientific situation-based scenario was used as a data collection tool. Data analysis consists of two stages. First, the graphs drawn by the prospective elementary mathematics teachers were scored with the descriptive analysis method.Then, the errors in the graphics drawn using the content analysis method were grouped and determined. When the data were analyzed, it was observed that a significant portion of prospective elementary mathematics teachers had deficiencies in their ability to draw graphs about the problem situation in the context of Covid-19. For this reason, when teaching graphics, drawing activities that require more context-based qualitative understanding or technology-assisted teaching applications can be used.
The aim of the study is to examine the graphing skills of prospective elementary mathematics teachers for a socioscientific problem situation related to Covid-19. The research is a qualitative ...research and was carried out with the case study method.The participants consisted of 43 prospective elementary mathematics teachers studying in the third year of a state university in Turkey. Typical case sampling, one of the purposive sampling methods, was used to determine the participants. In the research, an open-ended question that requires drawing three graphs with vital aspects based on a socio-scientific situation-based scenario was used as a data collection tool. Data analysis consists of two stages. First, the graphs drawn by the prospective elementary mathematics teachers were scored with the descriptive analysis method.Then, the errors in the graphics drawn using the content analysis method were grouped and determined. When the data were analyzed, it was observed that a significant portion of prospective elementary mathematics teachers had deficiencies in their ability to draw graphs about the problem situation in the context of Covid-19. For this reason, when teaching graphics, drawing activities that require more context-based qualitative understanding or technology-assisted teaching applications can be used.
We show an O(n)-time reduction from the problem of testing whether a multiset of positive integers can be partitioned into two multisets so that the sum of the integers in each multiset is equal to ...n/2 to the problem of testing whether an n-vertex biconnected outerplanar DAG admits an upward planar drawing. This constitutes the first barrier to the existence of efficient algorithms for testing the upward planarity of DAGs with no large triconnected minor.
We also show a result in the opposite direction. Suppose that partitioning a multiset of positive integers into two multisets so that the sum of the integers in each multiset is n/2 can be solved in f(n) time. Let G be an n-vertex biconnected outerplanar DAG and e be an edge incident to the outer face of an outerplanar drawing of G. Then it can be tested in O(f(n)) time whether G admits an upward planar drawing with e on the outer face.
A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints ...without any edge-intersection. In this paper we give a linear-time algorithm to find a grid drawing of any given 5-connected plane graph G with five or more vertices on the outer face. The size of the drawing satisfies W + H ≤ n−2, where n is the number of vertices in G, W is the width and H is the height of the grid drawing.
Abstract Evaluations—encompassing computational evaluations, benchmarks and user studies—are essential tools for validating the performance and applicability of graph and network layout algorithms ...(also known as graph drawing). These evaluations not only offer significant insights into an algorithm's performance and capabilities, but also assist the reader in determining if the algorithm is suitable for a specific purpose, such as handling graphs with a high volume of nodes or dense graphs. Unfortunately, there is no standard approach for evaluating layout algorithms. Prior work holds a ‘Wild West’ of diverse benchmark datasets and data characteristics, as well as varied evaluation metrics and ways to report results. It is often difficult to compare layout algorithms without first implementing them and then running your own evaluation. In this systematic review, we delve into the myriad of methodologies employed to conduct evaluations—the utilized techniques, reported outcomes and the pros and cons of choosing one approach over another. Our examination extends beyond computational evaluations, encompassing user‐centric evaluations, thus presenting a comprehensive understanding of algorithm validation. This systematic review—and its accompanying website—guides readers through evaluation types, the types of results reported, and the available benchmark datasets and their data characteristics. Our objective is to provide a valuable resource for readers to understand and effectively apply various evaluation methods for graph layout algorithms. A free copy of this paper and all supplemental material is available at osf.io , and the categorized papers are accessible on our website at https://visdunneright.github.io/gd‐comp‐eval/ .
Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient ...for bend minimization algorithms is the existence of an
orthogonal representation
that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. In this work, we generalize this idea to
ortho-radial representations
of
ortho-radial drawings
, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. Unlike the orthogonal case, there exist ortho-radial representations that do not admit a corresponding drawing, for example so-called strictly monotone cycles. An ortho-radial representation is called
valid
if it does not contain a strictly monotone cycle. Our first main result is that an ortho-radial representation admits a corresponding drawing if and only if it is valid. Previously such a characterization was only known for ortho-radial drawings of paths, cycles, and theta graphs (Hasheminezhad et al. in Australas J Combin 44:171–182, 2009), and in the special case of rectangular drawings of cubic graphs (Hasheminezhad et al. in Comput Geom 43(9):767–780, 2010), where the contour of each face is required to be a combinatorial rectangle. Additionally, we give a quadratic-time algorithm that tests for a given ortho-radial representation whether it is valid, and we show how to draw a valid ortho-radial representation in the same running time. Altogether, this reduces the problem of computing a minimum-bend ortho-radial drawing to the task of computing a valid ortho-radial representation with the minimum number of bends, and hence establishes an ortho-radial analogue of the topology-shape-metrics framework for planar orthogonal drawings by Tamassia (SIAM J Comput 16(3):421–444, 1987).
Design principles for origin-destination flow maps Jenny, Bernhard; Stephen, Daniel M.; Muehlenhaus, Ian ...
Cartography and geographic information science,
01/2018, Volume:
45, Issue:
1
Journal Article
Peer reviewed
Origin-destination flow maps are often difficult to read due to overlapping flows. Cartographers have developed design principles in manual cartography for origin-destination flow maps to reduce ...overlaps and increase readability. These design principles are identified and documented using a quantitative content analysis of 97 geographic origin-destination flow maps without branching or merging flows. The effectiveness of selected design principles is verified in a user study with 215 participants. Findings show that (a) curved flows are more effective than straight flows, (b) arrows indicate direction more effectively than tapered line widths, and (c) flows between nodes are more effective than flows between areas. These findings, combined with results from user studies in graph drawing, conclude that effective and efficient origin-destination flow maps should be designed according to the following design principles: overlaps between flows are minimized; symmetric flows are preferred to asymmetric flows; longer flows are curved more than shorter or peripheral flows; acute angles between crossing flows are avoided; sharp bends in flow lines are avoided; flows do not pass under unconnected nodes; flows are radially distributed around nodes; flow direction is indicated with arrowheads; and flow width is scaled with represented quantity.
