Search

Many data sets, crucial for today's applications, consist essentially of enormous networks, containing millions or even billions of elements. Having the possibility of visualizing such networks is of paramount importance. We propose an algorithmic framework and a visual metaphor, dubbed treebar map, to provide schematic representations of huge networks. Our goal is to convey the main features of the network's inner structure in a straightforward, two-dimensional, one-page drawing. This drawing effectively captures the essential quantitative information about the network's main components. Our experiments show that we are able to create such representations in a few hundreds of seconds. We demonstrate the metaphor's efficacy through visual examination of extensive graphs, highlighting how their diverse structures are instantly comprehensible via their representations., Comment: 27 pages, 32 figures, 1 table

In this paper, we initiate the study of quantum algorithms in the Graph Drawing research area. We focus on two foundational drawing standards: 2-level drawings and book layouts. Concerning $2$-level drawings, we consider the problems of obtaining drawings with the minimum number of crossings, $k$-planar drawings, quasi-planar drawings, and the problem of removing the minimum number of edges to obtain a $2$-level planar graph. Concerning book layouts, we consider the problems of obtaining $1$-page book layouts with the minimum number of crossings, book embeddings with the minimum number of pages, and the problem of removing the minimum number of edges to obtain an outerplanar graph. We explore both the quantum circuit and the quantum annealing models of computation. In the quantum circuit model, we provide an algorithmic framework based on Grover's quantum search, which allows us to obtain, at least, a quadratic speedup on the best classical exact algorithms for all the considered problems. In the quantum annealing model, we perform experiments on the quantum processing unit provided by D-Wave, focusing on the classical $2$-level crossing minimization problem, demonstrating that quantum annealing is competitive with respect to classical algorithms., 37 pages, 32 figures, 2 tables

A rectangular drawing of a planar graph $G$ is a planar drawing of $G$ in which vertices are mapped to grid points, edges are mapped to horizontal and vertical straight-line segments, and faces are drawn as rectangles. Sometimes this latter constraint is relaxed for the outer face. In this paper, we study rectangular drawings in which the edges have unit length. We show a complexity dichotomy for the problem of deciding the existence of a unit-length rectangular drawing, depending on whether the outer face must also be drawn as a rectangle or not. Specifically, we prove that the problem is NP-complete for biconnected graphs when the drawing of the outer face is not required to be a rectangle, even if the sought drawing must respect a given planar embedding, whereas it is polynomial-time solvable, both in the fixed and the variable embedding settings, if the outer face is required to be drawn as a rectangle., Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

We study a classic problem introduced thirty years ago by Eades and Wormald. Let $G=(V,E,\lambda)$ be a weighted planar graph, where $\lambda: E \rightarrow \mathbb{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 \in E$ is $\lambda(e)$. Cabello, Demaine, and Rote showed that the FEPR problem is NP-hard, even when $\lambda$ 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 its NP-hardness, even when $\lambda$ assigns to the edges only up to four distinct lengths. Conversely, we show that the FEPR problem is linear-time solvable when $\lambda$ 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 longest path., Comment: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

The algorithm of Tutte for constructing convex planar straight-line drawings and the algorithm of Floater and Gotsman for constructing planar straight-line morphs are among the most popular graph drawing algorithms. Surprisingly, little is known about the resolution of the drawings they produce. In this paper, focusing on maximal plane graphs, we prove tight bounds on the resolution of the planar straight-line drawings produced by Floater’s algorithm, which is a broad generalization of Tutte’s algorithm. Further, we use such a result to prove a lower bound on the resolution of the drawings of maximal plane graphs produced by Floater and Gotsman’s morphing algorithm. Finally, we show that such an algorithm might produce drawings with exponentially-small resolution, even when morphing drawings with polynomial resolution.

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)

An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other" inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such representations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a biconnected plane graph with "small" faces has a turn-regular orthogonal representation without bends., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Suppose that a biconnected graph is given, consisting of a large component plus several other smaller components, each separated from the main component by a separation pair. We investigate the existence and the computation time of schematic representations of the structure of such a graph where the main component is drawn as a disk, the vertices that take part in separation pairs are points on the boundary of the disk, and the small components are placed outside the disk and are represented as non-intersecting lunes connecting their separation pairs. We consider several drawing conventions for such schematic representations, according to different ways to account for the size of the small components. We map the problem of testing for the existence of such representations to the one of testing for the existence of suitably constrained $1$-page book-embeddings and propose several polynomial-time algorithms., Appeared in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Suppose that a biconnected graph is given, consisting of a large component plus several other smaller components, each separated from the main component by a separation pair. We investigate the existence and the computation time of schematic representations of the structure of such a graph where the main component is drawn as a disk, the vertices that take part in separation pairs are points on the boundary of the disk, and the small components are placed outside the disk and are represented as non-intersecting lunes connecting their separation pairs. We consider several drawing conventions for such schematic representations, according to different ways to account for the size of the small components. We map the problem of testing for the existence of such representations to the one of testing for the existence of suitably constrained 1-page book-embeddings and propose several polynomial-time and pseudo-polynomial-time algorithms.

We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex $u$ is represented by a geometric object $R(u)$ and in which each edge $(u,v)$ is represented by the intersection between $R(u)$ and $R(v)$ if it belongs to a dense subgraph or by a curve connecting the boundaries of $R(u)$ and $R(v)$ otherwise. We study a notion of planarity, called Clique Planarity, for intersection-link representations of graphs in which the dense subgraphs are cliques., 15 pages, 8 figures, extended version of 'Intersection-Link Representations of Graphs' (23rd International Symposium on Graph Drawing, 2015)

The Internet is constantly evolving and changing over time. Outages, attacks, upgrades, censorships, and policy changes modify the routing very frequently everywhere in the world. To give the possibility to the Internet Service Providers and to the network operators of monitoring such an evolving scenario, many organizations collect the routing changes and give free access to them. We propose, prototype, and evaluate a visual interface, called Upstream Visibility, to display such data. It is based on three views: (1) a global view that, based on stacked area charts, gives the high level trend of the visibility of an IP prefix; (2) a local view allows the user to check the effects over time of the visibility of an IP prefix on specific locations of the network; and (3) a traditional graph animation view. Also, we propose heuristics for producing such type of drawings, evaluating their effectiveness and performance against scenarios describing well-known Internet incidents.

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.

Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of $O(n)$ steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns' 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps., Comment: 31 pages, 18 figures

Federated networking is a promising approach to resource sharing that supports cost-effective services involving multiple parties. Research in this field largely focused on architectures and cost models, making limited progress on the technological side. On the other hand, the widely adopted Software-Defined Networking (SDN) model found its most successful application in data centers, exhibiting very little penetration in other scenarios. We leverage the unexplored potential of SDN on the edge of a network to introduce an approach that supports end-to-end connectivity among different federated partners. Our approach is based on simple Network Address and Port Translation (NAPT), making it applicable in standard IP networks. It is also very flexible, because it exploits SDN, and scalable, because address translations are performed on Customer Premises Equipment, where SDN is being progressively supported by device vendors. We define various alternative NAPT strategies and evaluate their effectiveness with simulations as well as emulated scenarios.

The Address Resolution Protocol (ARP) enables communication between IP-speaking nodes in a local network by reconstructing the hardware (MAC) address associated with the IP address of an interface. This is not needed in a Software-Defined Network (SDN), because each device can forward packets without the need to learn this association. We tackle the interoperability problem arising between standard network devices (end systems, routers), that rely on ARP, and SDN datapaths, that do not handle ARP packets natively. In particular, we propose a general approach to handle ARP in a SDN, that is applicable in several network scenarios, is transparent for existing devices, and can coexist with any packet forwarding logic implemented in the controller. Our approach reduces ARP traffic by confining it to the edge of SDNs and requires a minimal set of flow entries in the datapaths. We argument about its applicability and confirm it with experiments performed on SDN datapaths from a range of different vendors.

Internet Exchange Points (IXPs) play a crucial role in the Internet ecosystem. However, existing literature fails in quantitatively assessing the advantage for an Internet Service Provider (ISP) to peer at an IXP. We give a contribution to bridge such a gap by collaborating with three medium-sized ISPs in Italy to compare key performance indicators (round-trip delay, hop count, packet loss, and jitter) as measured from several vantage points in presence and absence of IXP peerings. Our findings are that IXP-based paths exhibit better and more stable performance, whereas avoiding IXPs introduces performance deterioration and higher variability. Moreover, our measurements confirm that IXP-based paths tend to preserve the locality of traffic.

Harmful Internet hijacking incidents put in evidence how fragile the Border Gateway Protocol (BGP) is, which is used to exchange routing information between Autonomous Systems (ASes). As proved by recent research contributions, 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. 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., Comment: 17 pages with 6 figures

Multi Protocol Label Switching (MPLS) Virtual Private Networks (VPNs) have seen an unparalleled increasing adoption in the last decade. Although their flexibility as transport technology and their effectiveness for traffic engineering are well recognized, VPNs are difficult to set up and manage, due to the complexity of configurations, to the number of involved protocols, and to the limited control and predictability of network behaviors. On the other hand, Software-Defined Networking (SDN) is a consolidated, yet still emerging paradigm by which the control plane logic of a network device is implemented by an arbitrarily programmed software that runs outside the device itself. We conjugate the effectiveness of traditional VPNs with the programmability of SDN, proposing a novel and improved realization of MPLS VPNs based on SDN. With our approach, provisioning and setup of VPNs are accomplished by using a simple and flexible configuration language. Management and troubleshooting are facilitated because only a minimal set of technologies (notably, just MPLS) is retained. Control and predictability of network behaviors are enhanced by the centralized coordination enforced by the SDN controller. Besides illustrating our proposed approach and specifying the configuration language, we describe a prototype implementation of a controller and the outcome of tests we conducted in several configuration scenarios.

A map graph is a contact graph of internally-disjoint regions of the plane, where the contact can be even a point. Namely, each vertex is represented by a simple connected region and two vertices are connected by an edge iff the corresponding regions touch.

Internet service providers (ISPs) run the internal Border Gateway Protocol (iBGP) to distribute interdomain routing information among their BGP routers. Previous research consistently assumed that iBGP is always configured as a mere dispatcher of interdomain routes. However, router configuration languages offer operators the flexibility of fine-tuning iBGP. In this paper, we study the impact of deploying routing policies in iBGP. First, we devise a provably correct inference technique to pinpoint iBGP policies from public BGP data. We show that the majority of large transit providers and many small transit providers do apply policies in iBGP. Then, we discuss how iBGP policies can help achieve traffic engineering and routing objectives. We prove that, unfortunately, the presence of iBGP policies exacerbates the iBGP convergence problem and invalidates fundamental assumptions for previous results, affecting their applicability. Hence, we propose provably correct configuration guidelines to achieve traffic engineering goals with iBGP policies, without sacrificing BGP convergence guarantees. Finally, for the cases in which our guidelines are not applicable, we propose a novel technique to verify the correctness of an iBGP configuration with iBGP policies. We implement a prototype tool and show the feasibility of offline analyses of arbitrary policies on both real-world and in vitro configurations.