1,721,146 research outputs found
Upward Planar Drawings and Switch-regularity Heuristics
No full textIn this paper we present a new characterization of switch-regular upward embeddings, a concept introduced by Di Battista and Liotta in 1998. This characterization allows us to define a new efficient algorithm for computing upward planar drawings of embedded planar digraphs. If compared with a popular approach described by Bertolazzi, Di Battista, Liotta, and Mannino, our algorithm computes drawings that are significantly better
in terms of total edge length and aspect ratio, especially for low-density digraphs. Also, we experimentally prove that the running time of the drawing process is reduced in most cases
Density of straight-line 1-planar graph drawings
No full textA 1-planar drawing of a graph is such that each edge is crossed at most once. In 1997,
Pach and Tóth showed that any 1-planar drawing with n vertices has at most 4n−8 edges
and that this bound is tight for n 12. We show that, in fact, 1-planar drawings with n
vertices have at most 4n−9 edges, if we require that the edges are straight-line segments.
We also prove that this bound is tight for infinitely many values of n>=8. Furthermore, we
investigate the density of 1-planar straight-line drawings with additional constraints on the
vertex positions. We show that 1-planar drawings of bipartite graphs whose vertices lie on
two distinct horizontal layers have at most 1.5n − 2 edges, and we prove that 1-planar
drawings such that all vertices lie on a circumference have at most 2.5n − 4 edges; both
these bounds are also tight
Fast layout computation of clustered networks: Algorithmic advances and experimental analysis
No full textThe 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 log n + 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
Computing Upward Planar Drawings Using Switch-Regularity Heuristics
No full textLet G be an upward planar embedded digraph. The classical
approach used to compute an upward drawing of G consists of two steps: (i) A planar st-digraph including G is constructed adding a suitable set of dummy edges; (ii) A polyline drawing of the st-digraph is computed using standard techniques, and dummy edges are then removed. For computational
reasons, the number of dummy edges added in the first step
should be kept as small as possible. However, as far as we know, there is only one algorithm known in the literature to compute an st-digraph including an upward planar embedded digraph. In this paper we describe an alternative heuristic, which is based on the concept of switch-regularity introduced by Di Battista and Liotta (1998). We experimentally prove that the new heuristic significantly reduces the number of dummy edges added to determine the including st-digraph. For digraphs with low density, such a reduction has a positive impact on the quality of the final drawing and on the overall running time required by the drawing process
Guest Editors' Foreword
No full textGuest Editors' Foreword of the JGAA special issue on Graph Drawing 2012
GDToolkit
No full textGDToolkit is an object-oriented graph drawing library, written in the C++ programming language. It offers many facilities that support users to develop specic graph visualization interfaces that can be used in real-world domains. The chapter describes the main functionalities and architectural aspects of this librar
Computing Orthogonal Drawings with the Minimum Number of Bends
No full textWe describe a branch-and-bound algorithm for computing an orthogonal grid drawing with the minimum number of bends of a biconnected planar graph. Such an algorithm is based on an efficient enumeration schema of the embeddings of a planar graph and on several new methods for computing lower bounds of the number of bends. We experiment with such algorithm on a large test suite and compare the results with the state-of-the-art. The experiments show the feasibility of the approach and also its limitations. Further, the experiments show how minimizing the number of bends has positive effects on other quality measures of the effectiveness of the drawing. We also present a new method for dealing with vertices of degree larger than four
A survey on graph drawing beyond planarity
No full textGraph 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
HV-planarity: Algorithms and complexity
No full textAn HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing, that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17]. On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three
- …
