Search

Documents

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 NP-completeness results and some polynomial-time algorithms. Building on such algorithms we develop a JavaScript library for NodeTrix representations aimed at reducing the crossings between edges incident to the same matrix., Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

Given a planar graph $G$ and a partition of the neighbors of each vertex $v$ in four sets $UR(v)$, $UL(v)$, $DL(v)$, and $DR(v)$, the problem Windrose Planarity asks to decide whether $G$ admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor $u \in UR(v)$ is above and to the right of $v$, (ii) each neighbor $u \in UL(v)$ is above and to the left of $v$, (iii) each neighbor $u \in DL(v)$ is below and to the left of $v$, (iv) each neighbor $u \in DR(v)$ is below and to the right of $v$, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with $n$ vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most $2n-5$ bends in total, which lies on the $3n \times 3n$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area., Appeared in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

Several projects deploy probes in the Internet. Probes are systems that continuously perform traceroutes and other networking measurements (e.g., ping) towards selected targets. Measurements can be stored and analyzed to gain knowledge on several aspects of the Internet, but making sense of such data requires suitable methods and tools for exploration and visualization. We present Radian, a tool that allows to visualize traceroute paths at different levels of detail and to animate their evolution during a selected time interval. We also describe extensive tests of the tool using traceroutes performed by RIPE Atlas Internet probes.

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, this 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 exists 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.

A greedy drawing is a graph drawing containing a distance-decreasing path for every pair of nodes. A path (v0,v1,…,vm) is distance-decreasing if d(vi,vm) < d(vi-1,vm), for i = 1,…,m. Greedy drawings easily support geographic greedy routing. Hence, a natural and practical problem is the one of constructing greedy drawings in the plane using few bits for representing vertex Cartesian coordinates and using the Euclidean distance as a metric. We show that there exist greedy-drawable graphs that do not admit any greedy drawing in which the Cartesian coordinates have less than a polynomial number of bits. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012 (A preliminary version of this article appeared at the International Symposium on Graph Drawing (GD '09).)

This paper describes algorithms for computing non-planar drawings of planar graphs in subquadratic area such that: (i) edge crossings are allowed only if they create large angles; (ii) the maximum number of bends per edge is bounded by a (small) constant.

We pose a new visualization challenge, asking Graph Drawing algorithms to cope with the requirements of Streaming applications. In this model a source produces a graph one edge at a time. When an edge is produced, it is immediately drawn and its placement cannot be altered. The drawing has an image persistence, that controls the lifetime of edges. If the persistence is k, an edge remains in the drawing for the time spent by the source to generate k edges, and then it fades away. In this model we study the area requirement of planar straight-line grid drawings of trees and we assess the output quality of the presented algorithms by computing the competitive ratio with respect to the best known offline algorithms.

This paper studies weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line drawings such that if the proximity region of two points p and q representing vertices is devoid of other points representing vertices, then segment ( p , q ) is allowed, but not forced, to appear in the drawing. This differs from the usual, strong, notion of proximity drawing in which such segments must appear in the drawing. Most previously studied proximity regions are associated with a parameter β , 0 ⩽ β ⩽ ∞ . For fixed β , weak β -drawability is at least as expressive as strong β -drawability, as a strong β -drawing is also a weak one. We give examples of graph families and β values where the two notions coincide, and a situation in which it is NP-hard to determine weak β -drawability. On the other hand, we give situations where weak proximity significantly increases the expressive power of β -drawability: we show that every graph has, for all sufficiently small β , a weak β -proximity drawing that is computable in linear time, and we show that every tree has, for every β less than 2, a weak β -drawing that is computable in linear time.

Consider a planar drawing ${\it \Gamma}$of a planar graph G such that the vertices are drawn as small circles and the edges are drawn as thin strips. Consider a cycle c of G. Is it possible to draw c as a non-intersecting closed curve inside ${\it \Gamma}$, following the circles that correspond in ${\it \Gamma}$to the vertices of c and the strips that connect them? We show that this test can be done in polynomial time and study this problem in the framework of clustered planarity for highly non-connected clustered graphs.

In this paper we study the clustered graphs whose underlying graph is a cycle. This is a simple family of clustered graphs that are “highly non connected”. We start by studying 3-cluster cycles, that are clustered graphs such that the underlying graph is a simple cycle and there are three clusters all at the same level. We show that in this case testing the c-planarity can be done efficiently and give an efficient drawing algorithm. Also, we characterize 3-cluster cycles in terms of formal grammars. Finally, we generalize the results on 3-cluster cycles considering clustered graphs that at each level of the inclusion tree have a cycle structure. Even in this case we show efficient c-planarity testing and drawing algorithms.

A wide number of practical applications would benefit from automatically generated graphical representations of database schemas, in which tables are represented by boxes, and table attributes correspond to distinct stripes inside each table. Links, connecting attributes of two different tables, represent referential constraints or join relationships, and may attach arbitrarily to the left- or to the right-hand side of the stripes representing the attributes. To our knowledge no drawing technique is available to automatically produce diagrams in such a strongly constrained drawing convention. In this paper we provide a polynomial time algorithm for solving this problem, and test its efficiency and effectiveness against a large test suite. Also, we describe an implementation of a system that uses such an algorithm and we study the main methodological problems we faced in developing such a technology.

DBdraw is an application that allows the user to automatically produce drawings of database schemas according to a drawing standard that is well accepted by the database community. The drawing engine of DBdraw is based on the GDToolkit library.

A wide number of practical applications would benefit from automatically generated graphical representations of relational schemas, in which tables are represented by boxes, and table attributes correspond to distinct stripes inside each table. Links, connecting two attributes of two different tables, represent relational constraits or join paths, and may attach arbitrarily to the left or to the right side of the stripes representing the attributes. To our knowledge no drawing technique is available to automatically produce diagrams in such strongly constrained drawing Convention. In this paper we provide a polynomial time algorithm solving this problem and test its efficiency and effectiveness against a large test suite.

In this paper we consider the important class of directed acyclic graphs (DAGs), and present the results of a comparative study on four popular drawing algorithms specifically developed for them. The study has been performed within a general experimental setting consisting of two large test suites of DAGs and a set of quality measures. The focus of the experiments has been the practical behavior of the algorithms with a geometric foundation compared to that of the algorithms with a topological foundation. The four algorithms exhibit various trade-offs with respect to the quality measures considered, and none of them clearly outperforms the others. Our analysis has motivated the development of a new hybrid strategy for drawing DAGs that performs quite well in practice.

HERMES is a system for exploring and visualizing Autonomous Systems and their interconnections. It relies on a three-tiers architecture, on a large repository of routing information coming from heterogeneous sources, and on sophisticated graph drawing engine. Such an engine exploits static and dynamic graph drawing techniques.

A digraph is upward planar if it has a planar drawing such that all the edges are monotone with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network structures, which frequently arise in software engineering, project management, and visual languages. In this paper we investigate upward planarity testing of single-source digraphs; we provide a new combinatorial characterization of upward planarity and give an optimal algorithm for upward planarity testing. Our algorithm tests whether a single-source digraph with n vertices is upward planar in O(n) sequential time, and in O(log n) time on a CRCW PRAM with $n \log \log n/\log n$ processors, using O(n,) space. The algorithm also constructs an upward planar drawing if the test is successful. The previously known best result is an O(n2)-time algorithm by Hutton and Lubiw [Proc. 2nd ACM--SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, pp. 203--211]. No efficient parallel algorithms for upward planarity testing were previously known.

We present a method for constructing orthogonal drawings of graphs of maximum degree six in three dimensions. Such a method is based on generating the final drawing through a sequence of steps, starting from a "degenerate" drawing. At each step the drawing "splits" into two pieces and finds a structure more similar to its final version. Also, we test the effectiveness of our approach by performing an experimental comparison with several existing algorithms.

We 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.

We present a tool for quick prototyping and testing graph drawing algorithms. The user interacts with the system through a diagrammatic interface. Algorithms are visually displayed as directed paths in a graph. The user can specify an algorithm by suitably combining the edges of a path. The implementation exploits the powerful functionalities of Diagram Server and has been experimented both as a research support tool and as a back-end of an industrial application.

Upward and dominance drawings of acyclic digraphs find important applications in the display of hierarchical structures such as PERT diagrams, subroutine-call charts, and is-a relationships. The combinatorial model underlying such hierarchical structures is often a series-parallel digraph. In this paper the problem of constructing upward and dominance drawings of series-parallel digraphs is investigated. We show that the area requirement of upward and dominance drawings of series-parallel digraphs crucially depends on the choice of planar embedding. Also, we present efficient sequential and parallel algorithms for drawing series-parallel digraphs. Our results show that while series-parallel digraphs have a rather simple and well understood combinatorial structure, naive drawing strategies lead to drawings with exponential area, and clever algorithms are needed to achieve optimal area.

In this paper we give a model for dynamic graph algorithms, based on performing queries and updates on an implicit representation of the drawing. We present dynamic algorithms for drawing planar graphs that use a variety of drawing standards (such as polyline, straight-line, orthogonal, grid, upward, and visibility drawings), and address aesthetic criteria that are important for readability, such as the display of planarity, symmetry, and reachability. Also, we provide techniques that are especially tailored for important subclasses of planar graphs such as trees and series-parallel digraphs. Our dynamic drawing algorithms have the important property of performing “smooth updates” of the drawing. Of special geometric interest is the possibility of performing point-location and window queries on the implicit representation of the drawing.

The goal of this paper is to investigate the area requirements for upward grid drawings of binary trees. First, we show that there is a family of binary trees with n vertices that require ω(n log n) area; this bound is tight to within a constant factor, i.e. any binary tree with n vertices can be drawn in O(n log n) area. Then we present an algorithm for constructing an upward drawing of a complete binary tree with n vertices in O(n) area, and, finally, we extend this result to the drawings of Fibonacci trees.

Consider a planar drawing Gamma of a planar graph G such that the vertices are drawn as small circles and the edges are drawn as thin stripes. Consider a non-simple cycle c of G. Is it possible to draw c as a non-intersecting closed curve inside Gamma, following the circles that correspond in Gamma to the vertices of c and the stripes that connect them? We show that this test can be done in polynomial time and study this problem in the framework of clustered planarity for highly non-connected clustered graphs.

We prove that, given two topologically-equivalent upward planar straight-line drawings of an $n$-vertex directed graph $G$, there always exists a morph between them such that all the intermediate drawings of the morph are upward planar and straight-line. Such a morph consists of $O(1)$ morphing steps if $G$ is a reduced planar $st$-graph, $O(n)$ morphing steps if $G$ is a planar $st$-graph, $O(n)$ morphing steps if $G$ is a reduced upward planar graph, and $O(n^2)$ morphing steps if $G$ is a general upward planar graph. Further, we show that $\Omega(n)$ morphing steps might be necessary for an upward planar morph between two topologically-equivalent upward planar straight-line drawings of an $n$-vertex path., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018) The current version is the extended one

In this paper we study the computational complexity of the Upward Planarity Extension problem, which takes as input an upward planar drawing Γ H of a subgraph H of a directed graph G and asks whether Γ H can be extended to an upward planar drawing of G. Our study fits into the line of research on the extensibility of partial representations, which has recently become a mainstream in Graph Drawing. We show the following results. – First, we prove that the Upward Planarity Extension problem is NP-complete, even if G has a prescribed upward embedding, the vertex set of H coincides with the one of G, and H contains no edge. – Second, we show that the Upward Planarity Extension problem can be solved in O ( n log ⁡ n ) time if G is an n-vertex upward planar st-graph. This result improves upon a known O ( n 2 ) -time algorithm, which however applies to all n-vertex single-source upward planar graphs. – Finally, we show how to solve in polynomial time a surprisingly difficult version of the Upward Planarity Extension problem, in which the underlying graph of G is a path or a cycle, G has a prescribed upward embedding, H contains no edges, and no two vertices share the same y-coordinate in Γ H .