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.

Documents

In this paper we study two problems related to the drawing of level graphs, that is, T-LEVEL PLANARITY and CLUSTERED-LEVEL PLANARITY. We show that both problems are NP-complete in the general case and that they become polynomial-time solvable when restricted to proper instances., 10 pages, 4 figures

The Internet is a huge and complex network in which Internet Service Providers (ISPs) compete for revenue. In order to support the establishment of commercial agreements, routing in the Internet must therefore allow each ISP to autonomously set up its own routing policies while ensuring global connectivity. The Border Gateway Protocol (BGP) allows to achieve both these goals, and is the currently adopted protocol for Internet routing. It can be shown that the interaction of not-so-unlikely BGP configurations adopted at different ISPs can cause permanent oscillations of routing. Several models and algorithms have been proposed in the literature to study routing oscillations. The goal of this paper is to provide a survey of state of the art contributions in this field with an emphasis on the algorithmic aspects.

ACM

One of the main concerns for an Internet Service Provider (ISP) is to optimize the distribution of network traffic among its upstream providers, for example to balance bandwidth usage, or to distribute link costs evenly. While outgoing traffic can be easily controlled, influencing the volumes of incoming traffic is more challenging. An effective and widely used technique to influence the distribution of incoming traffic is AS-path prepending, which consists in artificially inflating the length of the AS-path of BGP announcements. Since shorter AS-paths are often preferred, this can force incoming traffic to use different links. ISPs usually search for the optimal amount of prepending on a trial-and-error basis. In this work, we formulate the problem of finding the optimal amount of prepending as an Integer Linear Programming problem, which permits to consider several optimality criteria and to embody many constraints. We also show how efficient algorithms for the problem can be devised by considering it from a Computational Geometry perspective. We believe that, under reasonable assumptions, this theoretic approach can have interesting practical impacts.

The Internet has recently been object of several studies concerning its structural properties and the behavior of routing protocols. One of the most interesting challenges is the inference of commercial relationships between Autonomous Systems. This knowledge would provide a deeper insight into the laws governing routing processes, and would constitute a useful guideline for choosing connection strategies and device configurations. Several algorithms have been proposed for inferring the relationships on the basis of the routing data of the Border Gateway Protocol (BGP). This work aims at performing an analysis of the results produced by state-of-the-art algorithms, with the purpose of investigating the meaningfulness of such results. This is achieved by running the algorithms extensively on several BGP data sets and by observing how assigned relationships change. Two kinds of analysis are used for doing this: one considers the relationships assigned by the same algorithm on data sets relative to different time instants; the second takes into account the relationships assigned by different algorithms on the same data set. We a methodology and implement some tools for performing the two kinds of analysis and apply the methodology to two well known algorithms, using publicly available data sets. What comes out is that the number of AS pairs whose relationship is steadily assigned never falls below 94% of the overall pairs, and that the solutions computed by the two algorithms overlap for more than 90% of the pairs. This is an evidence of the fact that the inference is well-founded, i.e., it is not heavily influenced by routing oscillations, and that following different approaches almost yields the same solution, which further validates its trustworthiness.

Because of its practical relevance, the Border Gateway Protocol (BGP) has been the target of a huge research and industrial effort since more than a decade and a BGP routing theory has been developed out of that effort. In this paper, we show that there exists a mapping between BGP and a logic circuit. We show simple networks with routers with elementary BGP configurations that simulate logic gates, clocks and flip-flops, and we show how to interconnect them to simulate arbitrary logic circuits. We then investigate the implications of such a mapping on the computational complexity of BGP problems. We show that, under reasonable assumptions on message timings, BGP has the same computing power as a Turing Machine. As a consequence, we devise a new method for studying the complexity of analyzing BGP configurations and exploit such a method to give several new complexity bounds. Also, if message timings are unrestricted, BGP can simulate a combinational logic circuit, which allows us to prove the NP-hardness of a new variant of a well-known BGP problem. Finally, we investigate whether the mapping is still feasible when BGP policies are restricted, e.g., in iBGP or when Local Transit Policies or Gao-Rexford conditions are enforced.