Search

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 Ω (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. [ABSTRACT FROM AUTHOR]

In this paper, we show a polynomial-time algorithm for testing c -planarity of embedded flat clustered graphs with at most two vertices per cluster on each face. Our result is based on a reduction to the planar set of spanning trees in topological multigraphs (pssttm) problem, which is defined as follows. Given a (non-planar) topological multigraph A with k connected components A 1 , ... , A k , do spanning trees of A 1 , ... , A k exist such that no two edges in any two spanning trees cross? Kratochvíl et al. [SIAM Journal on Discrete Mathematics, 4(2): 223–244, 1991] proved that the problem is NP-hard even if k = 1 ; on the other hand, Di Battista and Frati presented a linear-time algorithm to solve the pssttm problem for the case in which A is a 1 -planar topological multigraph [Journal of Graph Algorithms and Applications, 13(3): 349–378, 2009]. For any embedded flat clustered graph C , an instance A of the pssttm problem can be constructed in polynomial time such that C is c -planar if and only if A admits a solution. We show that, if C has at most two vertices per cluster on each face, then it can be tested in polynomial time whether the corresponding instance A of the pssttm problem is positive or negative. Our strategy for solving the pssttm problem on A is to repeatedly perform a sequence of tests, which might let us conclude that A is a negative instance, and simplifications, which might let us simplify A by removing or contracting some edges. Most of these tests and simplifications are performed "locally", by looking at the crossings involving a single edge or face of a connected component A i of A ; however, some tests and simplifications have to consider certain global structures in A , which we call α -donuts. If no test concludes that A is a negative instance of the pssttm problem, then the simplifications eventually transform A into an equivalent 1 -planar topological multigraph on which we can apply the cited linear-time algorithm by Di Battista and Frati. [ABSTRACT FROM AUTHOR]

Harmful Internet hijacking incidents put in evidence how fragile interdomain routing is. In particular, the Border Gateway Protocol (BGP), which is used to exchange routing information between Internet entities, called Autonomous Systems (ASes), proved to be prone to attacks launched by a single malicious AS. Recent research contributions pointed out that even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. The goal of the attack is to attract a traffic flow towards the malicious AS. While in the hijacking attack connectivity between the endpoints of a flow can be disrupted, in the interception attack connectivity must be maintained. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E.g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception. [ABSTRACT FROM AUTHOR]

Inter-domain routing data and Internet active probing measurements are two types of information commonly available in huge datasets and subject to extensive, focused analysis. However, the study of the correlation between these two complementary types of information still remains one of the most challenging problems in today's research in networking. In this paper we describe a metaphor for the visualization of the interplay between the routing information exchanged via BGP and the round-trip delay measurements collected by several geolocated probes. We implemented a prototype based on the above metaphor. Our prototype highlights both the Autonomous System topology and the latency associated with each AS-path over time. Further, it shows how probes are partitioned into clusters associated with each border gateway, based on observed traffic patterns. The resulting visualization allows the user to explore the dynamics of the correlation between the two types of information. [ABSTRACT FROM AUTHOR]

We prove that planar graphs have O(log² n) queue number, thus improving upon the previous O(√n) upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in O(n log8 n) volume, thus improving upon the previous O(n3/2) upper bound. [ABSTRACT FROM AUTHOR]

We show that every plane graph admits a planar straight-line drawing in which all faces with more than three vertices are nonconvex polygons. [ABSTRACT FROM AUTHOR]

Abstract: Consider a planar drawing of a planar graph such that the vertices are drawn as small circles and the edges are drawn as thin stripes. Consider a non-simple cycle of . Is it possible to draw as a non-intersecting closed curve inside , following the circles that correspond in to the vertices of 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. [Copyright &y& Elsevier]

In Europe, the aim of achieving a knowledge-based society makes the quality of training systems a topic of crucial importance. Italy is also interested in working out strategies and tools for improving its training supply. To this end the Ministry of Labour asked a public research institute, the Institute for the Development of Workers' Vocational Training (ISFOL), to design a self-assessment tool (SAT) for evaluating the quality of regional training systems. The article tracks the logical and chronological course undertaken to design the SAT, bearing in mind the current conditions of Italian public authorities responsible for the programming, management and evaluation of vocational education and training policies. The SAT methodological choices and its design are described, as well as its application by all Italian central and northern regions. The article concludes by mapping out ways in which the SAT can be used and pointing out some still unresolved issues. [ABSTRACT FROM AUTHOR]

To devise effective network engineering strategies and to assess the quality of upstream providers, network operators would greatly benefit from the knowledge of which Internet paths might be traversed by the traffic flows entering their networks in the case of network faults or when traffic engineering measures are used. However, current methodologies do not provide this information. This paper presents methodologies to discover alternate paths that might be selected in the presence of network faults or different routing policies and to deduce the routing policies of other operators. The techniques are validated through extensive experimentation on the Internet. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

A diagram is a drawing on the plane that represents a graph-like structure, where nodes are represented by symbols and edges are represented by curves connecting pairs of symbols. An automatic layout facility is a tool that receives as input a graph-like structure and is able to produce a diagram that nicely represents such a structure. Many systems use diagrams in the interaction with the users; thus, automatic layout facilities and algorithms for graphs layout have been extensively studied in the last years. We present a new approach in designing an automatic layout facility. Our approach is based on a modular management of a large collection of algorithms and on a strategy that, given the requirements of an application, selects a suitable algorithm for such requirements. The proposed approach has been used for designing the automatic layout facility of Diagram Server, a network server that offers to its clients several facilities for managing diagrams. [ABSTRACT FROM AUTHOR]

The data dictionary contains the description of all types of data produced, managed, exchanged, and maintained in an organization. Data descriptions (very often hundreds of schemas) should be organized in such a way to allow all the users of the information system to understand the meaning of data and their relationships. In this paper, a new set of structuring primitives is presented for a dictionary of entity relationship data schemas. The formal properties of such structuring primitives ire investigated and the feasibility of their usage is shown by providing a methodology for dictionary design. [ABSTRACT FROM AUTHOR]

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(n²)-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. [ABSTRACT FROM AUTHOR]

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity , are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels. [ABSTRACT FROM AUTHOR]

A point set S⊆R2 is universal for a class G of planar graphs if every graph of G has a planar straight-line embedding on S. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a subquadratic universal point set still remains one of the most fascinating open problems in Graph Drawing. In this paper we make a major step towards a solution for this problem. Motivated by the fact that each point set of size n in general position is universal for the class of n-vertex outerplanar graphs, we concentrate our attention on k-outerplanar graphs. We prove that they admit an O(nlogn)-size universal point set in two distinct cases, namely when k=2 (2-outerplanar graphs) and when k is unbounded but each outerplanarity level is restricted to be a simple cycle (simply-nested graphs). [ABSTRACT FROM AUTHOR]

This article introduces the articles in the special issue on visualization applications and design studies. The articles cover both traditional application domains such as visualization of scientific simulations and emerging ones such as visualization of text streams, image collections, trajectories, and political phenomena. [ABSTRACT FROM PUBLISHER]

We study a classic problem introduced thirty years ago by Eades and Wormald. Let G = (V , E , λ) be a weighted planar graph, where λ : E → R + is a length function. The Fixed Edge-Length Planar Realization problem (FEPR for short) asks whether there exists a planar straight-line realization of G , i.e., a planar straight-line drawing of G where the Euclidean length of each edge e ∈ E is λ (e). Cabello, Demaine, and Rote showed that the FEPR problem is NP-hard, even when λ assigns the same value to all the edges and the graph is triconnected. Since the existence of large triconnected minors is crucial to the known NP-hardness proofs, in this paper we investigate the computational complexity of the FEPR problem for weighted 2-trees, which are K 4 -minor free. We show the NP-hardness of the problem, even when λ assigns to the edges only up to four distinct lengths. Conversely, we show that the FEPR problem is linear-time solvable when λ assigns to the edges up to two distinct lengths, or when the input has a prescribed embedding. Furthermore, we consider the FEPR problem for weighted maximal outerplanar graphs and prove it to be linear-time solvable if their dual tree is a path, and cubic-time solvable if their dual tree is a caterpillar. Finally, we prove that the FEPR problem for weighted 2-trees is slice-wise polynomial in the length of the large path. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper we study planar morphs between planar straight-line grid drawings of trees. A morph consists of a sequence of morphing steps, where in a morphing step vertices move along straight-line trajectories at constant speed. We show how to construct planar morphs that simultaneously achieve a reduced number of morphing steps and a polynomially-bounded resolution. We assume that both the initial and final drawings lie on the grid and we ensure that each morphing step produces a grid drawing; further, we consider both upward drawings of rooted trees and drawings of arbitrary trees. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we analyze the relationships among different planar embeddings of the same graph and study how two planar embeddings can be morphed one into the other with the minimum number of elementary changes, while preserving the mental map of the user. We call this problem Topological Morphing, in analogy with the well-known Geometric Morphing problem, in which it is studied how two planar drawings can be morphed one into the other with the minimum number of elementary changes. First, we define two operations, called flip and skip, describing natural transformations of a graph embedding that preserve the mental map of the user. Then, we study the problem of performing a morph while minimizing the number of these operations. We show that the Topological Morphing problem is NP-hard for biconnected planar graphs, we give polynomial-time algorithms for some restricted versions of the problem, and, based on such polynomial-time algorithms, we give a fixed-parameter tractable algorithm for the general case. [Copyright &y& Elsevier]

A simple topological graph is k -quasiplanar (k ≥ 2) if it contains no k pairwise crossing edges, and k -planar if no edge is crossed more than k times. In this paper, we explore the relationship between k -planarity and k -quasiplanarity to show that, for k ≥ 2 , every k -planar simple topological graph can be transformed into a (k + 1) -quasiplanar simple topological graph. [ABSTRACT FROM AUTHOR]