A rectilinear-upward planar drawing of a digraph G is a crossing-free drawing of G where each edge is either a horizontal or a vertical segment, and such that no directed edge points downward. Rectilinear-Upward Planarity Testing is the problem of deciding whether a digraph G admits a rectilinear-upward planar drawing. We study the complexity of Rectilinear-Upward Planarity Testing and provide several algorithmic results. Precisely, we prove that: ( i ) the problem is NP-complete, even if G is biconnected; ( i i ) it can be solved in linear time when an upward planar embedding of G is fixed; ( i i i ) the problem is polynomial-time solvable for biconnected digraphs of treewidth at most two, i.e., for digraphs whose underlying undirected graph is a series-parallel graph; ( i v ) the problem is fixed-parameter tractable (namely, fixed-parameter linear) for all biconnected graphs, when parameterized by the number of sources and sinks in the digraph. • We study the algorithmic complexity of a problem that combines two well-established topics in graph drawing, namely rectilinear planar drawings and upward planar drawings. This problems, called rectilinear-upward planarity testing, asks to decide whether an input planar di-graph admits a planar drawing where each edge is either a horizontal or a vertical segment, and no edge points downwards. • We prove that rectilinear-upward planarity testing is NP-complete, even for biconnected digraphs. • We provide a linear-time algorithm for rectilinear-upward planarity testing of digraphs with a fixed upward planar embedding. • We provide a quadratic-time algorithm for rectilinear-upward planarity testing of biconnected partial 2-trees (i.e., digraphs whose underlying undirected graph is series-parallel) in the variable embedding setting. • We provide a fixed-parameter linear (FPL) algorithm for rectilinear- upward planarity testing of general biconnected digraphs in the variable embedding setting.

We study a question that lies at the intersection of classical research subjects in Topological Graph Theory and Graph Drawing: Computing a drawing of a graph with a prescribed number of crossings on a given set S of points, while ensuring that its curve complexity (i.e., maximum number of bends per edge) is bounded by a constant. We focus on trees: Let T be a tree, ϑ(T) be its thrackle number, and χ be any integer in the interval [0,ϑ(T)]. In the tangling phase we compute a topological linear embedding of T with ϑ(T) edge crossings and a constant number of spine traversals. In the untangling phase we remove edge crossings without increasing the spine traversals until we reach χ crossings. The computed linear embedding is used to construct a drawing of T on S with χ crossings and constant curve complexity. Our approach gives rise to an O(n²)-time algorithm for general trees and an O(n log n)-time algorithm for paths. We also adapt the approach to compute RAC drawings, i.e. drawings where the angles formed at edge crossings are π/2.

We address the problem of computing a dynamic visualization of a geometric graph G as a sequence of frames. Each frame shows only a portion of the graph but their union covers G entirely. The two main requirements of our dynamic visualization are: (i) guaranteeing drawing stability, so to preserve the user’s mental map; (ii) keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of G. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph.

BACKGROUND: Cophylogeny reconciliation is a powerful method for analyzing host-symbiont coevolution. The cophylogeny problem consists of mapping the phylogenetic tree of the symbionts into the one of the hosts, including events such as duplications, co-speciation, host-switches, and extinctions by comparing the discrepancies between the topologies of the associated symbiont evolutionary trees. Visualizing tree reconciliations is important for biologists as it aids in understanding and identifying specific patterns in the coevolution of hosts and symbionts. Additionally, when multiple optimal solutions exist, it allows for the quick comparison of different reconciliations between the same pair of trees. RESULTS: Here, we present VIRI (visual inspector of reconciliation instances), a new tree reconciliation visualizer. We adopt a hybrid metaphor combining space-filling (for host trees) and node-link (for symbiont trees) approaches, implementing the algorithms described in Calamoneri et al. (Theor Comput Sci 815:228-245. https://doi.org/10.1016/j.tcs.2019.12.024 , 2020). The visualizations produced by VIRI are designed to be clear and interpretable, thanks to an unambiguous, top-down layout of tree reconciliations and the preservation of the user's mental map when comparing multiple reconciliations on the same pair of trees. In particular, the consistent use of a shared host tree layout across visualizations is a novel feature that facilitates direct comparison. Moreover, VIRI proposes a crossing-free visualization whenever possible. Finally, VIRI allows users to store datasets and download their visualizations, offering a convenient way to organize and share data. An example of visualization produced by VIRI is depicted in Fig. 1. CONCLUSIONS: VIRI efficiently produces clear and easy-to-read visualizations of tree reconciliations. VIRI is free and available at https://viri.di.uniroma1.it/ .

We study upward pointset embeddings (UPSEs) of planar $st$-graphs. Let $G$ be a planar $st$-graph and let $S \subset \mathbb{R}^2$ be a pointset with $|S|= |V(G)|$. An UPSE of $G$ on $S$ is an upward planar straight-line drawing of $G$ that maps the vertices of $G$ to the points of $S$. We consider both the problem of testing the existence of an UPSE of $G$ on $S$ (UPSE Testing) and the problem of enumerating all UPSEs of $G$ on $S$. We prove that UPSE Testing is NP-complete even for $st$-graphs that consist of a set of directed $st$-paths sharing only $s$ and $t$. On the other hand, if $G$ is an $n$-vertex planar $st$-graph whose maximum $st$-cutset has size $k$, then UPSE Testing can be solved in $O(n^{4k})$ time with $O(n^{3k})$ space; also, all the UPSEs of $G$ on $S$ can be enumerated with $O(n)$ worst-case delay, using $O(k n^{4k} \log n)$ space, after $O(k n^{4k} \log n)$ set-up time. Moreover, for an $n$-vertex $st$-graph whose underlying graph is a cycle, we provide a necessary and sufficient condition for the existence of an UPSE on a given pointset, which can be tested in $O(n \log n)$ time. Related to this result, we give an algorithm that, for a set $S$ of $n$ points, enumerates all the non-crossing monotone Hamiltonian cycles on $S$ with $O(n)$ worst-case delay, using $O(n^2)$ space, after $O(n^2)$ set-up time.

Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most $k$ times for some integer $k \ge 1$. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-$k$-planarity is NP-complete already for $k=1$ and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.

An abstract topological graph (AT-graph) is a pair $A=(G,\mathcal{X})$, where $G=(V,E)$ is a graph and $\mathcal{X} \subseteq {E \choose 2}$ is a set of pairs of edges of $G$. A realization of $A$ is a drawing $Γ_A$ of $G$ in the plane such that any two edges $e_1,e_2$ of $G$ cross in $Γ_A$ if and only if $(e_1,e_2) \in \mathcal{X}$; $Γ_A$ is simple if any two edges intersect at most once (either at a common endpoint or at a proper crossing). The AT-graph Realizability (ATR) problem asks whether an input AT-graph admits a realization. The version of this problem that requires a simple realization is called Simple AT-graph Realizability (SATR). It is a classical result that both ATR and SATR are NP-complete. In this paper, we study the SATR problem from a new structural perspective. More precisely, we consider the size $\mathrmλ(A)$ of the largest connected component of the crossing graph of any realization of $A$, i.e., the graph ${\cal C}(A) = (E, \mathcal{X})$. This parameter represents a natural way to measure the level of interplay among edge crossings. First, we prove that SATR is NP-complete when $\mathrmλ(A) \geq 6$. On the positive side, we give an optimal linear-time algorithm that solves SATR when $\mathrmλ(A) \leq 3$ and returns a simple realization if one exists. Our algorithm is based on several ingredients, in particular the reduction to a new embedding problem subject to constraints that require certain pairs of edges to alternate (in the rotation system), and a sequence of transformations that exploit the interplay between alternation constraints and the SPQR-tree and PQ-tree data structures to eventually arrive at a simpler embedding problem that can be solved with standard techniques.

Many data sets, crucial for today’s applications, consist 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 Maps, 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, that effectively captures the essential quantitative information about the network’s main components. 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.

Datacenters are a critical part of the Internet infrastructure as they guarantee efficient deployment of a wide range of services. Since a considerable amount of datacenter failures is caused by software bugs and configuration errors, the management and testing of these networks is a crucial task. In this field, emulation-based digital twins have proven their effectiveness. To faithfully emulate the typical three layers hierarchy, composed of physical servers, virtual machines, and containers, the support for nested virtualization is a fundamental requirement. Further, the emulation of hyper-scale datacenters needs to leverage on horizontal scaling over a cluster of nodes. Existing container-based proposals do not meet both requirements. On the contrary, existing VM-based proposals meet such requirements, but they need complex configurations and high resource demands. We propose a container-based framework to faithfully emulate datacenters. This is a fundamental building block for designing datacenter digital twins, that would allow testing of real software implementations in a lightweight, scalable, and easily configurable environment.

Abstract A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The kUBE Testing problem, which asks whether a graph admits a kUBE, was introduced in 1999 by Heath, Pemmaraju, and Trenk (SIAM J Comput 28(4), 1999). In a companion paper, Heath and Pemmaraju (SIAM J Comput 28(5), 1999) proved that the problem is linear-time solvable for $$k=1$$ k = 1 and NP-complete for $$k = 6$$ k = 6 . Closing this gap has been a central question in algorithmic graph theory since then. In this paper, we make a major contribution towards a definitive answer to the above question by showing that kUBE Testing is NP-complete for $$k\ge 3$$ k ≥ 3 , even for st-graphs, i.e., acyclic directed graphs with a single source and a single sink. Indeed, our result, together with a recent work of Bekos et al. (Theor Comput Sci 946, 2023) that proves the NP-completeness of 2UBE for planar st-graphs, closes the question about the complexity of the kUBE problem for any k. Motivated by this hardness result, we then focus on the 2UBE Testing for planar st-graphs. On the algorithmic side, we present an $$O(f(\beta )\cdot n+n^3)$$ O ( f ( β ) · n + n 3 ) -time algorithm for 2UBE Testing, where $$\beta $$ β is the branchwidth of the input graph and f is a singly-exponential function on $$\beta $$ β . Since the treewidth and the branchwidth of a graph are within a constant factor from each other, this result immediately yields an FPT algorithm for st-graphs of bounded treewidth. Furthermore, we describe an O(n)-time algorithm to test whether a plane st-graph whose faces have a special structure admits a 2UBE that additionally preserves the plane embedding of the input st-graph. On the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving $$2$$ 2 UBE.

Given a bipartite graph G = (Vb, Vr, E), the 2-Level Quasi-Planarity problem asks for the existence of a drawing of G in the plane such that the vertices in Vb and in Vr lie along two parallel lines ℓb and ℓr, respectively, each edge in E is drawn in the unbounded strip of the plane delimited by ℓb and ℓr, and no three edges in E pairwise cross. We prove that the 2-LEVEL Quasi-Planarity problem is NP-complete. This answers an open question of Dujmović, Pór, and Wood. Furthermore, we show that the problem becomes linear-time solvable if the ordering of the vertices in Vb along ℓb is prescribed. Our contributions provide the first results on the computational complexity of recognizing quasi-planar graphs, which is a long-standing open question. Our linear-time algorithm exploits several ingredients, including a combinatorial characterization of the positive instances of the problem in terms of the existence of a planar embedding with a caterpillar-like structure, and an SPQR-tree-based algorithm for testing the existence of such a planar embedding. Our algorithm builds upon a classification of the types of embeddings with respect to the structure of the portion of the caterpillar they contain and performs a computation of the realizable embedding types based on a succinct description of their features by means of constant-size gadgets.

Abstract We focus on the automatic detection of communities in large networks, a challenging problem in many disciplines (such as sociology, biology, and computer science). Humans tend to associate to form families, villages, and nations. Similarly, the elements of real-world networks naturally tend to form highly connected groups. A popular model to represent such structures is the clique, that is, a set of fully interconnected nodes. However, it has been observed that cliques are too strict to represent communities in practice. The k-plex relaxes the notion of clique, by allowing each node to miss up to k connections. Although k-plexes are more flexible than cliques, finding them is more challenging as their number is greater. In addition, most of them are small and not significant. In this paper we tackle the problem of finding only large k-plexes (i.e., comparable in size to the largest clique) and design a meta-algorithm that can be used on top of known enumeration algorithms to return only significant k-plexes in a fraction of the time. Our approach relies on: (1) methods for strongly reducing the search space and (2) decomposition techniques based on the efficient computation of maximal cliques. We demonstrate experimentally that known enumeration algorithms equipped with our approach can run orders of magnitude faster than full enumeration.

We introduce an ETSI NFV compliant, scalable, and distributed architecture, called Megalos, that supports the implementation of virtual network scenarios consisting of virtual devices (VNFs) where each VNF may have several L2 interfaces assigned to virtual LANs. We rely on Docker containers to realize VNFs and we leverage Kubernetes for the management of the nodes of a distributed cluster. Our architecture guarantees the segregation of each virtual LAN traffic from the traffic of other LANs, from the cluster traffic, and from Internet traffic. Also, a packet is only sent to the cluster node containing the recipient VNF. The allocation of the VNFs to the nodes of the cluster is performed by Megalos Scheduler, taking into account the network topology in order to reduce the traffic among nodes. We produce an example application where we emulate a large network scenario, with thousands of VNFs and LANs, on a small cluster of 50 nodes. Finally, we experimentally show the scalability potential of Megalos by measuring the overhead of the distributed environment and of its signaling protocols.

This paper addresses a long standing, widely studied, open question: Given a planar 3-graph G (i.e., a planar graph with vertex degree at most three), what is the best computational upper bound to compute a bend-minimum planar orthogonal drawing of G in the variable embedding setting? In this setting the algorithm can choose among the exponentially many planar embeddings of G the one that leads to an orthogonal drawing with the minimum number of bends. We answer the question by describing a linear-time algorithm that computes a bend-minimum planar orthogonal drawing of G. Also, if G is not K4, the drawing has at most one bend per edge. The existence of an orthogonal drawing Г of a planar 3-graph such that Г has the minimum number of bends and at most one bend per edge was previously unknown.

We present a novel approach for the detection of 2-plexes, a popular relaxation of cliques used for modeling network communities. Specifically, with the purpose of identifying theoretically sound methods for community detection on a large scale, we introduce the first shared-nothing distributed algorithm for this problem. This result opens a new research direction for scalable community detection. Our proposal has three main ingredients: (i) we reduce the problem of finding 2-plexes to that of finding cliques; (ii) we leverage known algorithms for fast computation of cliques; (iii) we exploit a decomposition technique for a distributed shared-nothing computation. Preliminary experiments on a 10-nodes cluster running Spark confirm the effectiveness of our approach.

We study $k$-page upward book embeddings ($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on $k$ pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a $k$UBE is NP-complete for $k\geq 3$. A hardness result for this problem was previously known only for $k = 6$ [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on $k=2$. On the algorithmic side, we present polynomial-time algorithms for testing the existence of $2$UBEs of planar $st$-graphs with branchwidth $β$ and of plane $st$-graphs whose faces have a special structure. These algorithms run in $O(f(β)\cdot n+n^3)$ time and $O(n)$ time, respectively, where $f$ is a singly-exponential function on $β$. Moreover, on the combinatorial side, we present two notable families of plane $st$-graphs that always admit an embedding-preserving $2$UBE.

Attributed graphs model real networks by enriching their nodes with attributes accounting for properties. Several techniques have been proposed for partitioning these graphs into clusters that are homogeneous with respect to both semantic attributes and to the structure of the graph. However, time and space complexities of state of the art algorithms limit their scalability to medium-sized graphs. We propose SToC (for Semantic-Topological Clustering), a fast and scalable algorithm for partitioning large attributed graphs. The approach is robust, being compatible both with categorical and with quantitative attributes, and it is tailorable, allowing the user to weight the semantic and topological components. Further, the approach does not require the user to guess in advance the number of clusters. SToC relies on well known approximation techniques such as bottom-k sketches, traditional graph-theoretic concepts, and a new perspective on the composition of heterogeneous distance measures. Experimental results demonstrate its ability to efficiently compute high-quality partitions of large scale attributed graphs.

K-plexes are a formal yet flexible way of defining communities in networks. They generalize the notion of cliques and are more appropriate in most real cases: while a node of a clique C is connected to all other nodes of C, a node of a k-plex may miss up to k connections. Unfortunately, computing all maximal k-plexes is a gruesome task and state-of-the-art algorithms can only process small-size networks. In this paper we propose a new approach for enumerating large k-plexes in networks that speeds up the search by several orders of magnitude, leveraging on (i) methods for strongly reducing the search space and (ii) efficient techniques for the computation of maximal cliques. Several experiments show that our strategy is effective and is able to increase the size of the networks for which the computation of large k-plexes is feasible from a few hundred to several hundred thousand nodes.

We study a family of algorithms, introduced by Chan [SODA 1999], for drawing ordered rooted binary trees. Any algorithm in this family (which we name an LR-algorithm) takes in input an ordered rooted binary tree T with a root rT, and recursively constructs drawings of the left subtree L of rT and of the right subtree R of rT; then either it applies the left rule, i.e., it places one unit below and to the left of rT, and one unit below with the root of R vertically aligned with rT, or it applies the right rule, i.e., it places one unit below and to the right of rT, and ΓL one unit below with the root of L vertically aligned with rT. In both cases, the edges between rT and its children are represented by straight-line segments. Different LR- algorithms result from different choices on whether the left or right rule is applied at any node of T. We are interested in constructing LR-drawings (that are drawings obtained via LR-algorithms) with small width. Chan showed three LR- algorithms that achieve, for an n-node ordered rooted binary tree, width O(n0.695), width O(n0.5), and width O(n0.48). We prove that, for every n-node ordered rooted binary tree, an LR-drawing with minimum width can be constructed in O(n1.48) time. Further, we show an infinite family of n-node ordered rooted binary trees requiring Ω(n°.418) width in any LR-drawing; no lower bound better than n(log n) was previously known. Finally, we present the results of an experimental evaluation that allowed us to determine the minimum width of all the ordered rooted binary trees with up to 455 nodes. Our interest in LR-drawings is mainly motivated by a result of Di Battista and Frati [Algorithmica 2009], who proved that n-vertex outerplanar graphs have outerplanar straight-line drawings in O(n1.48) area by means of a drawing algorithm which resembles an LR-algorithm. We deepen the connection between LR-drawings and outerplanar drawings by proving that, if n-node ordered rooted binary trees have LR-drawings with f (n) width, for any function f (n), then n-vertex outerplanar graphs have outerplanar straight-line drawings in O(f (n)) area. Finally, we exploit a structural decomposition for ordered rooted binary trees introduced by Chan in order to prove that every n-vertex outerplanar graph has an outer-planar straight-line drawing in area.

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.

Dynamic network visualization aims at representing the evolution of relational information in a readable, scalable, and effective way. A natural approach, called 'time-to-time mapping', consists of computing a representation of the network at each time step and animating the transition between subsequent time steps. However, recent literature recommends to represent time-related events by means of static graphic counterparts, realizing the so called 'time-to-space mapping'. This paradigm has been successfully applied to networks where nodes and edges are subject to a restricted set of events: appearances, disappearances, and attribute changes. In this paper we describe NetFork, a system that conveys the timings and the impact of path changes that occur in a routing network by suitable time-to-space metaphors, without relying on the time-to-time mapping adopted by the play-back interfaces of alternative network monitoring tools. A user study and a comparison with the state of the art show that users can leverage on high level static representations to quickly assess the quantity and quality of the path dynamics that took place in the network.

The detection of communities in social networks is a challenging task. A rigorous way to model communities considers maximal cliques, that is, maximal subgraphs in which each pair of nodes is connected by an edge. State-of-the-art strategies for finding maximal cliques in very large networks decompose the network in blocks and then perform a distributed computation. These approaches exhibit a trade-off between efficiency and completeness: decreasing the size of the blocks has been shown to improve efficiency but some cliques may remain undetected since high-degree nodes, also called hubs, may not fit with all their neighborhood into a small block. In this paper, we present a distributed approach that, by suitably handling hub nodes, is able to detect maximal cliques in large networks meeting both completeness and efficiency. The approach relies on a two-level decomposition process. The first level aims at recursively identifying and isolating tractable portions of the network. The second level further decomposes the tractable portions into small blocks. We demonstrate that this process is able to correctly detect all maximal cliques, provided that the sparsity of the network is bounded, as it is the case of real-world social networks. An extensive campaign of experiments confirms the effectiveness, efficiency, and scalability of our solution and shows that, if hub nodes were neglected, significant cliques would be undetected.

Network operators invest significant resources in monitoring and troubleshooting the infrastructure they run. Currently, the availability of large networks of probing devices, like, for example, RIPE Atlas, dramatically increases the amount of data an operator can rely on. In particular, the large amount of traceroutes they can produce are both an opportunity and a challenge. In this paper we provide a detailed description of RoutingWatch, a visual tool for interactively performing searches and analysis of routing events inferred from a large set of traceroutes. The key design choices of RoutingWatch are based on discussions with network operators. We evaluate the effectiveness of our approach by conducting a preliminary user study.

We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each vertex along a piecewise linear curve with linear complexity. The linear bound is asymptotically optimal in the worst case.

Bitcoin is a digital currency whose transactions are stored into a public ledger, called blockchain, that can be viewed as a directed graph with more than 70 million nodes, where each node represents a transaction and each edge represents Bitcoins flowing from one transaction to another one. We describe a system for the visual analysis of how and when a flow of Bitcoins mixes with other flows in the transaction graph. Such a system relies on high-level metaphors for the representation of the graph and the size and characteristics of transactions, allowing for high level analysis of big portions of it.

We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G , can such a drawing be extended to a planar drawing of the entire graph G ? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.” These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time. Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem Simultaneous Embedding with Fixed Edges (Sefe) . There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with the same outer face, there exists a morph (i.e., a continuous transformation) between the two drawings so that the drawing remains straight-line planar at all times. Cairns's original proof required exponentially many morphing steps. We prove that there is a morph that consists of O(n2) steps, where each step is a linear morph that moves each vertex at constant speed along a straight line. Using a known result on compatible triangulations this implies that for a general planar graph G and any two straight-line planar drawings of G with the same embedding, there is a morph between the two drawings that preserves straight-line planarity and consists of O(n4) steps.

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

Many different approaches have been proposed for the challenging problem of visually analyzing large networks. Clustering is one of the most promising. In this paper, we propose a new clustering technique whose goal is that of producing both intracluster graphs and intercluster graph with desired topological properties. We formalize this concept in the (X,Y) -clustering framework, where Y is the class that defines the desired topological properties of intracluster graphs and X is the class that defines the desired topological properties of the intercluster graph. By exploiting this approach, hybrid visualization tools can effectively combine different node-link and matrix-based representations, allowing users to interactively explore the graph by expansion/contraction of clusters without loosing their mental map. As a proof of concept, we describe the system Visual Hybrid (X,Y)-clustering (VHYXY) that implements our approach and we present the results of case studies to the visual analysis of social networks.

Many different approaches have been proposed for the challenging problem of visually analyzing large networks. Clustering is one of the most promising. In this paper we propose a new goal for clustering that is especially tailored to hybrid-visualization tools. Namely, that of producing both intra-cluster graphs and inter-cluster graph that are suitable for highly-readable visualizations within different representation conventions. We formalize this concept in the (X,Y)-clustering framework, where Y is the class that defines the desired topological properties of intra-cluster graphs and X is the class that defines the desired topological properties of the inter-cluster graph. By exploiting this approach hybrid-visualization tools can effectively combine different node-link and matrix-based representations, allowing the users to interactively explore the graph by expansion/contraction of clusters without loosing their mental map. As a proof of concept, we describe the system VHYXY (Visual Hybrid (X,Y)-clustering) that integrates our techniques and we present the results of case studies to the visual analysis of co-authorship networks.

Compliance with the Gao-Rexford conditions [1] is perhaps the most realistic explanation of Internet routing stability, although BGP is renowned to be prone to oscillations. Informally, the Gao-Rexford conditions assume that (i) the business relationships between Internet Service Providers (ISPs) yield a hierarchy, (ii) each ISP behaves in a rational way, i.e., it does not offer transit to other ISPs for free, and (iii) each ISP ranks routes through customers better than routes through providers and peers.

We study the following problem: Given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the paradigm of extending a partial solution to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes hard an otherwise easy problem, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmata which show that the planarity of partially embedded graphs meets the “on-cas” behaviour – obvious necessary conditions for planarity are also sufficient. These conditions are expressed in terms of the interplay between (a) rotation schemes and containment relationships between cycles and (b) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we improve our algorithm to reach linear-time complexity. Finally, we consider several generalizations of the problem, e.g. minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. Also, we show how our algorithm can be applied to solve related Graph Drawing problems.

We propose a novel, passive, nonintrusive method to measure the one-way delay ofallthe packets flowing between customer sites connected by a provider backbone. Our approach does not sample traffic and requires the injection of a negligible amount of control packets, possibly none. This is obtained by deploying a Measurement Agent in each customer site and exploiting a covert channel to carry information about each packet that transits between the Measurement Agents. Further, we address the theoretical problems of encoding measurement information into the very limited amount of bits made available by the covert channel, obtaining one-way delay measurements with predictable accuracy. Finally, we experimentally validate the applicability of our approach.

For an Internet Service Provider (ISP), the knowledge of which interdomain paths could be traversed by its BGP announcements - and thus traffic flows - is essential to predict the impact of network faults, to develop effective traffic engineering and peering strategies, and to assess the quality of upstream providers. However, current methodologies do not provide this information. We present methodologies to discover how the BGP announcements for an ISP’s prefix are propagated through the Internet using withdrawals and specially crafted AS-sets. The techniques allow an ISP to determine which paths could be traversed in the presence of network faults or different routing policies on the ISP’s part and to deduce the routing policies of other ISPs with respect to its network. We validate our techniques through experimentation in the IPv6 and IPv4 Internet, showing that they can be safely and effectively applied in real-world situations.

We propose a new metaphor for the visualization of prefixes propagation in the Internet. Such a metaphor is based on the concept of topographic map and allows to put in evidence the relative importance of the Internet Service Providers (ISPs) involved in the routing of the prefix. Based on the new metaphor we propose an algorithm for computing layouts and experiment with such algorithm on a test suite taken from the real Internet. The paper extends the visualization approach of the BGPlay service, which is an Internet routing monitoring tool widely used by ISP operators.

Tunnels are widely used to improve security and to expand networks without having to deploy native infrastructure, and play an important role in the migration to IPv6. In this paper we introduce a number of techniques to detect, and collect information about IPv6-in-IPv4 tunnels. We also show how a known tunnel can be used as a "vantage point" to launch third-party tunnel-discovery explorations, scaling up the discovery process. We describe our Tunneltrace tool, which implements the proposed techniques, and validate them by means of a wide experimentation on the 6bone tunneled network, on the GARR network, and through the test boxes deployed worldwide by the RIPE NCC as part of the Test Traffic Measurements Service. We assess to what extent 6bone registry information is coherent with the actual network topology, and we provide the first experimental results on the current distribution of IPv6-in-IPv4 tunnels in the Internet, showing that even "native" networks reach more than 60% of all IPv6 prefixes through tunnels.

Tunnels are widely used to improve security and to expand networks without having to deploy native infrastructure. They play an important role in the migration to IPv6, which relies on IPv6-in-IPv4 tunnels where native connectivity is not available. However, tunnels offer lower performance and are less than native links. In this paper we introduce a number of techniques to detect, and collect information about, IPv6-in-IPv4 tunnels, and show how a known tunnel can be used as a "vantage point" to launch third-party tunnel-discovery explorations, scaling up the discovery process. We describe our Tunneltrace tool, which implements the proposed techniques, and validate them by means of a wide experimentation on the 6bone tunneled network, on native networks in Italy, the Netherlands, and Japan, and through the test boxes deployed worldwide by the RIPE NCC as part of the Test Traffic Measurements Service. We assess to what extent 6bone registry information is coherent with the actual network topology, and we provide the first experimental results on the current distribution of IPv6-in-IPv4 tunnels in the Internet, showing that even "native" networks reach more than 60 percent of all IPv6 prefixes through tunnels. Furthermore, we provide historical data on the migration to native IPv6, showing that the impact of tunnels in the IPv6 Internet did not significantly decrease over a six-month period. Finally, we briefly touch on the security issues posed by IPv6-in-IPv4 tunnels, discussing possible threats and countermeasures.

The problem of computing the types of the relationships between Internet autonomous systems is investigated. We refer to the model introduced in (ref.1), (ref.2) that bases the discovery of such relationships on the analysis of the AS paths extracted from the BGP routing tables. We characterize the time complexity of the above problem, showing both NP-completeness results and efficient algorithms for solving specific cases. Motivated by the hardness of the general problem, we propose heuristics based on a novel paradigm and show their effectiveness against publicly available data sets. The experiments put in evidence that our heuristics performs significantly better than state of the art heuristics.

Abstract 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. Copyright © 2002 John Wiley & Sons, Ltd.