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.

Numerous research contributions and monitoring systems in Interdomain Routing rely on data captured from specific vantage points on the Internet, referred to as Collector Peers, and collected by entities known as Route Collectors. In this paper, we first argue that current methods used to determine whether Collector Peers and Route Collectors are functioning correctly within a specific time frame are unreliable. To address this, we propose a method to assess the accuracy of the existing measurement framework. Our approach focuses on identifying sequences of update messages within Interdomain signaling, analyzing their start and end times, as well as their frequencies. We validate the accuracy of our method through two steps: (1) Analyzing sequences generated by a set of 'beacons' that emit Interdomain signaling at various frequencies, in order to evaluate our ability to characterize these sequence frequencies. (2) Assessing our ability to identify malfunctioning Collector Peers by comparing our results with known faults, which serve as the ground truth.

We study the following question, which has been considered since the 90’s: Does every st-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed y-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of st-planar graphs that always admit a planar straight-line dominance drawing. These include st-planar 3-trees in which every stacking operation introduces two edges incoming into the new vertex, st-planar graphs in which every vertex is adjacent to the sink, and st-planar graphs in which no face has the left boundary that is a single edge.

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the dependency digraph GP(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V (GP(I))|√δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).

A drawing of a graph divides the plane into topologically connected regions, called faces (or cells ). The boundary of each face is formed by vertices, crossings, and edge portions. Given a positive integer , we say that is a -real face drawing of if the boundary of each face of contains at least vertices of . Graphs that admit a -real face drawing are -real face graphs ; they have been studied so far in terms of edge density and inclusion relationships with other notable classes of nonplanar graphs that can be drawn avoiding specific crossing configurations. In this paper, we investigate the complexity of recognizing -real face graphs, that is, the complexity of testing whether a given graph is -real face, for desired values of . We study both the general unconstrained scenario and the 2-layer scenario in which the graph is bipartite, the vertices of the two partition sets lie on two distinct horizontal layers, and the edges are drawn as straight-line segments. While we prove NP-completeness results for the unconstrained scenario, we describe efficient recognition algorithms for the 2-layer setting.

We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an n -vertex bipartite graph G = ( U , V , E ⊆ U × V ) , a 2 -level drawing ( π U , π V ) of G is described by a linear ordering π U : U ↔ { 1 , … , | U | } of U and linear ordering π V : V ↔ { 1 , … , | V | } of V . For a fixed linear ordering π U of U , the OSCM problem seeks to find a linear ordering π V of V that yields a 2-level drawing ( π U , π V ) of G with the minimum number of edge crossings. We show that OSCM can be viewed as a set problem over V amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [ Quantum Speedups for Exponential-Time Dynamic Programming Algorithms . SODA 2019] to devise a QRAM-based algorithm that solves OSCM in ⁎ O ⁎ ( 1.728 n ) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in ⁎ O ⁎ ( 2 n ) time and polynomial space.

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.

We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. We show that OSCM can be viewed as a set problem amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA 2019] to devise a QRAM-based algorithm that solves OSCM in 𝒪^*(1.728ⁿ) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in 𝒪^*(2ⁿ) time and polynomial space.

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.

Several data centers adopt fat-tree topologies, where high bisection bandwidth is achieved by interconnecting commodity hardware and by using specific routing solutions. These solutions, which include protocol implementations and configurations, are difficult to evaluate and test both for the density of fat-trees and for the complexity of the protocols. Also, since most issues show up only when a fault happens, it is unfeasible to perform such tests in a production environment. Additionally, the lack of standard testing procedures motivates an effort in developing solutions for such a critical task. In this paper, we propose a methodology devised for testing fat-tree routing protocol implementations. It adopts a wall-clock independent method to establish metrics, which permits normalizing the results of different routing protocol implementations independently from the execution environment. The methodology is implemented by Sibyl, a software framework developed to perform repeatable tests on arbitrary fat-tree topologies automatically. Sibyl also provides a set of tools to analyze the results and investigate implementation behaviors. We evaluate the methodology and Sibyl in three use cases. Such use cases witness a wide spectrum of situations where Sibyl is effective for analyzing, comparing, developing, and debugging routing protocol implementations.

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.

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.

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

Network Function Virtualization (NFV) and Software-Defined Networking (SDN) are deeply changing the networking field by introducing software at any level, aiming at decoupling the logic from the hardware. Together, they bring several benefits, mostly in terms of scalability and flexibility. Up to now, SDN has been used to support NFV from the routing and the architectural point of view. In this paper we present Kathará, a framework based on containers, that allows network operators to deploy Virtual Network Functions (VNFs) through the adoption of emerging data-plane programmable capabilities, such as P4-compliant switches. It also supports the coexistence of SDN and traditional routing protocols in order to set up arbitrarily complex networks. As a side effect, thanks to Kathará, we demonstrate that implementing NFV by means of specific-purpose equipment is feasible and it provides a gain in performance while preserving the benefits of NFV. We measure the resource consumption of Kathará and we show that it performs better than frameworks that implement virtual networks using virtual machines by several orders of magnitude.

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.

Given a planar graph G and a partition of the neighbors of each vertex v in four sets v ↗ , v ↖ , v ↙ , and v ↘ , the problem W indrose P lanarity asks to decide whether G admits a windrose-planar drawing , that is, a planar drawing in which (i) each neighbor u ∈ v ↗ v is above and to the right of v , (ii) each neighbor u ∈ v ↖ is above and to the left of v , (iii) each neighbor u ∈ v ↙ is below and to the left of v , (iv) each neighbor u ∈ 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 us 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 2 n −5 bends in total, which lies on the 3 n × 3 n grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

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.

Internet eXchange Points (IXPs) serve as landmarks where many network service providers meet to obtain reciprocal connectivity. Some of them, especially the largest, offer route servers as a convenient technology to simplify the setup of a high number of bi-lateral peerings. Due to their potential to support a quick and easy interconnection among the networks of multiple providers, IXPs are becoming increasingly popular and widespread, and route servers are exploited increasingly often. However, in an ever-growing level of market competition, service providers are pushed to develop concerns about many aspects that are strategic for their business, ranging from commercial agreements with other members of an IXP to the policies that are adopted in exchanging routing information with them. Although these aspects are notoriously sensitive for network service providers, current IXP architectures offer no guarantees to enforce the privacy of such business-critical information. We re-design a traditional route server and propose an approach to enforce the privacy of peering relationships and routing policies that it manages. Our proposed architecture ensures that nobody, not even a third party, can access such information unless it is the legitimate owner (i.e., the IXP member that set up the policy), yet allowing the route server to apply the requested policies and each IXP member to verify that such policies have been correctly deployed. We implemented the route server and tested our solutions in a simulated environment, tracking and analyzing the number of exchanged control plane messages.

Federated networks have primarily emerged to support cloud computing services, in order to reduce costs for providers, as well as to increase their incomes. Up to now, the research activity has been mostly focused on architectures and cost models, setting aside technological aspects. In this paper, we propose SDNS, an SDN-system that opens the application fields of federated networks to federated connectivity services. By exploiting the centralized architecture offered by SDN and relying on the OpenFlow protocol, the most adopted enabler for SDN, we propose a way to easily interact with the Domain Name System (DNS) traffic in order to allow communication among multiple customers connected to different providers in presence of any type of IP address plan. We tested the scalability of our approach in a prototype implementation based on Netkit, a widely adopted simulation environment. We measured several control-plane overhead metrics, like the number of DNS, OpenFlow, and SDNS messages exchanged in the network. Our experiments show that the scalability of our method is essentially the same of the DNS service.

Mininet is the de-facto standard simulation environment for experimenting with SDN enabled networks based on the OpenFlow protocol. Although Mininet is powerful and not resource hungry, it has a strong limitation: it is not possible to use it for networks in which both OpenFlow and standard distributed routing protocols (e.g. Open Short Path First, OSPF) simultaneously run. In this paper we present SDNetkit, an enhanced release of the widely used Netkit network emulator that overcomes the limitation imposed by Mininet. We improved Netkit by adding all needed software to run OpenFlow based networks (e.g. OpenVSwitch and the Ryu framework). We show two use cases in which OpenFlow and standard protocols coexist. In particular, we address interoperability problems by presenting one use case in which OpenFlow nodes interact with standard ones (e.g. OSPF routers) in multi-domain networks, as well as one use case in which the OpenFlow protocol and OSPF run on the same machine, discussing some problems related to specific configurations. We believe that having the possibility to experiment SDN also in presence of interoperability scenarios results in opening to new research perspectives.

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.

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.

Given a planar graph G(V, E) and a partition of the neighbors of each vertex v ∊ V in four sets , and , 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 ∊ is above and to the right of v, (ii) each neighbor u ∊ is above and to the left of v, (iii) each neighbor u ∊ is below and to the left of v, (iv) each neighbor u ∊ 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 -hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar drawing we show how to construct one with at most one bend per edge on an O(n) × O(n) grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

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.

Virtual Private Networks (VPNs) implemented by Multi Protocol Label Switching (MPLS) tunnels appear in the service offer of many Internet Service Providers (ISPs). Due to the number of technologies that they involve and to the intricacy of their interactions, provisioning, setup, and maintenance of VPNs is a cumbersome task, whose complexity is usually mitigated by using advanced network management systems. We cut these difficulties at their roots by taking advantage of Software Defined Networking (SDN). We showcase the design and a prototype implementation of an SDN controller that, starting from a centralized specification of VPN settings expressed in a high-level simple and flexible language, automatically fills flow tables to implement the requested VPNs. Our implementation of VPNs with SDN promptly reacts to network dynamics (e.g., newly appeared links) and simplifies management a lot by dropping many unneeded technologies.

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.

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.

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.

Internal routing inside an ISP network is the foundation for lots of services that generate revenue from the ISP's customers. A fine-grained control of paths taken by network traffic once it enters the ISP's network is therefore a crucial means to achieve a top-quality offer and, equally important, to enforce SLAs. Many widespread network technologies and approaches (most notably, MPLS) offer limited (e.g., with RSVP-TE), tricky (e.g., with OSPF metrics), or no control on internal routing paths. On the other hand, recent advances in the research community are a good starting point to address this shortcoming, but miss elements that would enable their applicability in an ISP's network. We extend pathlet routing by introducing a new control plane for internal routing that pursues the following qualities: it is designed to operate in the internal network of an ISP; it enables fine-grained management of network paths with suitable configuration primitives; it is scalable because routing changes are only propagated to the network portion that is affected by the changes; it supports independent configuration of specific network portions without the need to know the configuration of the whole network; it is robust thanks to the adoption of multipath routing; it supports the enforcement of QoS levels; it is independent of the specific data plane used in the ISP's network; it can be incrementally deployed and it can nicely coexist with other control planes. Besides formally introducing the dissemination mechanisms and algorithms of our control plane, we propose an experimental validation in the simulation framework OMNeT++ that we use to assess the effectiveness and scalability of our approach.

Because of its practical relevance, the Border Gateway Protocol (BGP) has been the target of a huge research effort since more than a decade. In particular, many contributions aimed at characterizing the computational complexity of BGP-related problems. In this paper, we answer computational complexity questions by unveiling a fundamental mapping between BGP configurations and logic circuits. Namely, we describe simple networks containing 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 feasibility of solving BGP fundamental problems, and prove that, under realistic assumptions, BGP has the same computing power as a Turing Machine. We also investigate the impact of restrictions on the expressiveness of BGP policies and route propagation (e.g., route propagation rules in iBGP and Local Transit Policies in eBGP) and the impact of different message timing models. Finally, we show that the mapping is not limited to BGP and can be applied to generic routing protocols that use several metrics.

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 prove that planar graphs have $O(\log^2 n)$ queue number, thus improving upon the previous $O(\sqrt n)$ upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in $O(n \log^8 n)$ volume, thus improving upon the previous $O(n^{3/2})$ upper bound.

The flexibility and ease of setup of MPLS Virtual Private Networks (VPNs) and Virtual Private LAN Service (VPLS) motivate the large and growing user base of these services. It is therefore important for an Internet Service Provider (ISP) to ensure their uninterrupted operation, as also specified in service contracts. Although network monitoring is regarded as an essential activity to pursue this goal, existing monitoring approaches are often limited in the ability to capture the effects of VPN-related events such as reconfigurations and device failures. In this paper we provide several contributions: 1) a methodology to monitor the status of MPLS VPN and VPLS over time, which considers the BGP signaling messages sent by routers to propagate VPN information; the methodology is founded on an analysis of the observable effects of network events; it also envisions presenting the status of MPLS VPN and VPLS in an easy-to-understand visual form that allows to immediately spot potential anomalies; 2) an extensive discussion of the tradeoff between scalability of our monitoring approach and visibility of the effects of network events; 3) an architecture and prototype implementation of a tool based on our methodology; 4) a thorough experimentation of our approach in a realistic network scenario. As an example, the methodology allowed us to spot a subtle routing anomaly triggered by an implementation choice in the routing software used in our experiments.

Abstract A greedy drawing is a graph drawing containing a distance‐decreasing path for every pair of nodes. A path ( v 0 , v 1 ,…, v m ) is distance‐decreasing if d ( v i , v m ) < d ( v i ‐1 , v m ), for i = 1,…, m . Greedy drawings easily support geographic greedy routing. Hence, a natural and practical problem is the one of constructing greedy drawings in the plane using few bits for representing vertex Cartesian coordinates and using the Euclidean distance as a metric. We show that there exist greedy‐drawable graphs that do not admit any greedy drawing in which the Cartesian coordinates have less than a polynomial number of bits. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

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

The four articles in this special section presents extended versions of several outstanding papers from the IEEE Pacific Visualization Symposium 2011 (PacificVis 2011) which was held in Hong Kong, China, on 1-4 March 2011. The objective of this annual symposium is to foster greater exchange between visualization researchers and practitioners, and to draw more researchers in the Asia-Pacific region to enter this fascinating and rapidly growing area of research.

Welcome to the proceedings of the IEEE Pacific Visualization Symposium 2011 which took place in Hong Kong, China, on March 1–4, 2011. After a very successful event in Kyoto in 2008, Beijing in 2009, and Taipei in 2010, this is the fourth PacificVis sponsored by the IEEE Visualization and Graphics Technical Committee (VGTC).

BGP, the core protocol of the Internet backbone, is renowned to be prone to oscillations. Despite prior work shed some light on BGP stability, many problems remain open. For example, determining how hard it is to check that a BGP network is safe, i.e., it is guaranteed to converge, has been an elusive research goal up to now. In this paper, we address several problems related to BGP stability, stating the computational complexity of testing if a given configuration is safe, is robust, or is safe under filtering. Further, we determine the computational complexity of checking popular sufficient conditions for stability. We adopt a model that captures Local Transit policies, i.e., policies that are functions only of the ingress and the egress points. The focus on Local Transit policies is motivated by the fact that they represent a configuration paradigm commonly used by network operators. We also address the same BGP stability problems in the widely adopted SPP model. Unfortunately, we find that the most interesting problems are computationally hard even if policies are restricted to be as expressive as Local Transit policies. Our findings suggest that the computational intractability of BGP stability be an intrinsic property of policy-based path vector routing protocols that allow policies to be specified in complete autonomy.

Internet Service Providers can enforce a fine-grained control of Interdomain Routing by cleverly configuring the Border Gateway Protocol. However, the price to pay for the flexibility of BGP is the lack of convergence guarantees. The literature on network protocol design introduced several sufficient conditions that routing policies should satisfy to guarantee convergence. However, a methodology to systematically check BGP policies for convergence is still missing. This paper presents two fundamental contributions. First, we describe a heuristic algorithm that statically checks BGP configurations for guaranteed routing convergence. Our algorithm has several highly desirable properties: i) it exceeds state-of-the-art algorithms by correctly reporting more configurations as stable, ii) it can be implemented efficiently enough to analyze Internet-scale configurations, iii) it is free from false positives, namely never reports a potentially oscillating configuration as stable, and iv) it can help spot troublesome points in a detected oscillation. Second, we propose an architecture for a modular tool that exploits our algorithm to process native router configurations and report the presence of potential oscillations. Such a tool can effectively integrate syntactic checkers and assist operators in verifying configurations. We validate our approach using a prototype implementation and show that it scales well enough to enable Internet-scale convergence checks.

Border Gateway Protocol (BGP) allows providers to express complex routing policies preserving high degrees of autonomy. However, unrestricted routing policies can adversely impact routing stability. A key concept to understand the interplay between autonomy and expressiveness on one side, and stability on the other side, is safety under filtering, i.e., guaranteed stability under autonomous usage of route filters. BGP route filters are used to selectively advertise specific routes to specific neighbors. In this paper, we provide a characterization of safety under filtering, filling the large gap between previously known necessary and sufficient conditions. Our characterization is based on the absence of a particular kind of dispute wheel, a structure involving circular dependencies among routing preferences. We exploit our result to show that networks admitting multiple stable states are provably unsafe under filtering, and the troublesome portion of the configuration can be pinpointed starting from the stable states alone. This is especially interesting from an operational point of view since networks with multiple stable states actually happen in practice (BGP wedgies). Finally, we show that adding filters to an existing configuration may lead to oscillations even if the configuration is safe under any link failure. Unexpectedly, we find policy configurations where misconfigured filters can do more harm than network faults.

We prove that planar graphs have poly-logarithmic queue number, thus improving upon the previous polynomial upper bound. Consequently, planar graphs admit 3D straight-line crossing-free grid drawings in small volume.

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.

Internet Service Providers (ISPs) run the internal flavor of the Border Gateway Protocol (iBGP) for distributing routing information among border routers. While configuration languages allow routers to change iBGP attributes as a BGP message travels within the ISP's network, most prior work neglected this possibility, focusing only on the common case where iBGP attributes are left untouched. In this paper we aim at understanding what are the pros and cons of changing iBGP attributes. We estimate how many ISPs change iBGP attributes, and we motivate such a practice by showing usage scenarios where modified iBGP attributes yield better traffic engineering. We also revisit a well-studied problem in iBGP, that is, routing stability. We show that changing iBGP attributes can generate routing oscillations which are not possible otherwise, and are not detectable by state-of-the-art algorithms. We present a technique to check for routing oscillations even when iBGP attributes are changed, and we give simple guidelines for changing iBGP attributes while preserving stability.

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.

BGP allows providers to express complex routing policies preserving high degrees of autonomy. However, unrestricted routing policies can adversely impact routing stability. A key concept to understand the interplay between autonomy and expressiveness on one side, and stability on the other side, is safety under filtering, i.e., guaranteed stability under autonomous usage of route filters. BGP route filters are used to selectively advertise specific routes to specific neighbors. We provide a necessary and sufficient condition for safety under filtering, filling the large gap between previously known necessary and sufficient conditions. Our characterization is based on the absence of a particular kind of dispute wheel, a structure involving circular dependencies among routing preferences. We exploit our result to show that networks admitting multiple stable states are provably unsafe under filtering. This is especially interesting from an operational point of view, since networks with multiple stable states actually happen in practice (BGP wedgies). Finally, we show that adding filters to an existing configuration may lead to oscillations even if the configuration is safe under any link failure. Unexpectedly, we find policy configurations where misconfigured filters can do more harm than network faults.

Internet Service Providers can enforce a fine grained control of Interdomain Routing by cleverly configuring the Border Gateway Protocol. However, the price to pay for the flexibility of BGP is the lack of convergence guarantees. Network protocol design literature introduced several sufficient conditions that routing policies should satisfy to guarantee convergence. However, to our knowledge, none of these conditions has yet been exploited to automatically check BGP policies for convergence.

The policy-oriented nature of BGP provides network operators with great flexibility and control over the interdomain routing, nevertheless researchers showed that these benefits come at the cost of stability and predictability. In particular, policy interactions often separate, both in time and space, the effects of network events from their causes, making it hard to assess and debug network configurations.

Interdomain routes change over time, and it is impressive to observe up to which extent. Routes may change many times in the same day and sometimes in the same hour or minute. Such changes are caused by several types of events, e.g., a routing policy variation in an ISP, a router reboot, or a link fault. In this paper we do a step towards the identification of the cause of route changes, a problem that is attracting increasing attention from both researchers and network administrators. Namely, we propose a methodology for analyzing a given BGP route change in order to, at least partially, locate the event that triggered the change. The methodology is supported by a publicly available on-line service.

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.

Article Share on Clustered planarity Authors: Pier Francesco Cortese Universitá Roma Tre, Italia Universitá Roma Tre, ItaliaView Profile , Giuseppe Di Battista Universitá Roma Tre, Italia Universitá Roma Tre, ItaliaView Profile Authors Info & Claims SCG '05: Proceedings of the twenty-first annual symposium on Computational geometryJune 2005 Pages 32–34https://doi.org/10.1145/1064092.1064093Online:06 June 2005Publication History 15citation415DownloadsMetricsTotal Citations15Total Downloads415Last 12 Months10Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.

Graph drawing plays an important role in the solution of many information visualization problems. Most of the graph drawing algorithms are accompanied by a theoretical analysis of their characteristics, but only extensive experimentations can assess the practical performance of graph drawing algorithms in real-life applications. In this paper, we describe the results of some of the most popular experimental studies on graph drawing algorithms. Each study presents an in-depth comparative analysis on a specific class of algorithms, namely, algorithms for orthogonal drawings, interactive algorithms, algorithms for hierarchical drawings, and force-directed and randomized algorithms. Copyright © 2000 John Wiley & Sons, Ltd.

We deal with the problem of constructing the orthogonal drawing of a graph with the minimum number of bends along the edges. The problem has been recently shown to be NP-complete in the general case. In this paper we introduce and study the new concept of spirality, which is a measure of how an orthogonal drawing is "rolled up," and develop a theory on the interplay between spirality and number of bends of orthogonal drawings. We exploit this theory to present polynomial time algorithms for two significant classes of graphs: series-parallel graphs and 3-planar graphs. Series-parallel graphs arise in a variety ofproblems such as scheduling, electrical networks, data-flow analysis, database logic programs, and circuit layout. Also, they play a central role in planarity problems. Furthermore, drawings of 3-planar graphs are a classical field of investigation.

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 2 )-time algorithm by Hutton and Lubiw [Proc. 2nd ACM--SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, pp. 203--211]. No efficient parallel algorithms for upward planarity testing were previously known.

We describe a branch-and-bound algorithm for computing an orthogonal grid drawing with the minimum number of bends of a biconnected planar graph. Such algorithm is based on an efficient enumeration schema of the embeddings of a planar graph and on several new methods for computing lower bounds of the number of bends. We experiment such algorithm on a large test suite and compare the results with the state-of-the-art. The experiments show how minimizing the number of bends strongly improves several quality measures of the effectiveness of the drawing. We also present a graphic tool with animation that embodies the algorithm and allows interacting with all the phases of the computation.

The on-line planarity-testing problem consists of performing the following operations on a planar graph G: (i) testing if a new edge can be added to G so that the resulting graph is itself planar; (ii) adding vertices and edges such that planarity is preserved. An efficient technique for on-line planarity testing of a graph is presented that uses $O(n)$ space and supports tests and insertions of vertices and edges in $O(\log n)$ time, where n is the current number of vertices of G. The bounds for tests and vertex insertions are worst-case and the bound for edge insertions is amortized. We also present other applications of this technique to dynamic algorithms for planar graphs.

We give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating its angles; we also discuss minimality properties of the characterization. The characterization can be used: (1) to decide in linear time whether a given distribution of angles between the edges of a planar triangular graph can result in a planar drawing; (2) to reduce the problem of maximizing the minimum angle in a planar straight-line drawing of a planar triangular graph to a nonlinear optimization problem purely on a space of angles; (3) to give a characterization of the planar drawings of a triconnected graph through a system of equations and inequalities relating its angles; (4) to give a characterization of Delaunay triangulations through a system of equations and inequalities relating its angles; (5) to give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating the lengths of its edges; in turn, this result allows us to give a new characterization of the disc-packing representations of planar triangular graphs.

Article Free Access Share on An experimental comparison of three graph drawing algorithms (extended abstract) Authors: Giuseppe Di Battista D.I.F. A., Univ. della Basilicata, 85100 Potenza, Italy D.I.F. A., Univ. della Basilicata, 85100 Potenza, ItalyView Profile , Ashim Garg Dept. of Computer Science, Brown University, Providence, RI Dept. of Computer Science, Brown University, Providence, RIView Profile , Giuseppe Liotta Dip. Informatica e Sistemistica, Univ. di Roma 'La Sapienza', 00198 Roma, Italy Dip. Informatica e Sistemistica, Univ. di Roma 'La Sapienza', 00198 Roma, ItalyView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 306–315https://doi.org/10.1145/220279.220312Online:01 September 1995Publication History 10citation960DownloadsMetricsTotal Citations10Total Downloads960Last 12 Months8Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Drawing graphs is an important problem that combines elements of computational geometry and graph theory. Applications can be found in a variety of areas including circuit layout, network management, software engineering, and graphics. The main contributions of this paper can be summarized as follows: • We devise a model for dynamic graph algorithms, based on performing queries and updates on an implicit representation of the drawing, and we show its applications. • We present efficient dynamic drawing algorithms for trees and series-parallel digraphs. As further applications of the model, we give dynamic drawing algorithms for planar $st$-digraphs and planar graphs. Our algorithms adopt a variety of representations (e.g., straight line, polyline, visibility) and update the drawing in a smooth way.

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

We give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating its angles, solving a problem that is explicitly mentioned as open by several authors; we also discuss minimalit y properties of the charact erization.The characterization can be used: (1) to decide in linear time whether a given distribution of angles between the edges of a planar triangular graph can result in a planar drawing; (2) to tackle the problem of maximizing the minimum angle of the drawing of a planar triangular graph by studying the solution-space of a non-linear optimization problem; (3) to give a characterization of the planar drawings of a triconnected graph through a system of equations and inequalities relating its angles; (4) to give a characterization of Delaunay triangulations through a system of equations and inequalities relating its angles; (5) to give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating the length of its edges; in turn, this result allows to give a new characterization of the disc packing represent ations of planar triangular graphs.

We show that, for any fixed k, there exists an optimal O(n)-space compact representation of a k-connected graph G with n vertices, such that one can determine in O(1) time whether two vertices areconnectedbyk+l vertex-dkjoint paths, or are separated by k vertices/edges.Previously, the existence of such compact representations was known only for k <3.1 Summary of ResultsA fundamental issue for the fault-tolerance and reliabilityofnetworksis determining the existence of multiple disjoint paths connecting two nodes.In this paper we investigate the problem of constructing a compact representation of a graph so that one can test quickly for the existence of such paths.

An entity relationship oriented model, that includes the notion of class, together with different types of assertions on classes, is presented. The assertions are used to model IS-A and disjointness relations both between entities and between relationships, part-of relations between entities and relationships, mandatory participation of an entity in a relationship, and interdependencies between the projections of relationships. The semantics of the model are defined in terms of first-order logic, and a sound and complete inference algorithm for such a model is presented. The algorithm is shown to have polynomial time complexity in the case where interdependencies on the projections of relationships are not taken into account. It is suggested that the model and the associated inference capabilities provide a suitable formal basis for designing an effective environment supporting conceptual modeling.>

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. To this end, a set of structuring primitives for a dictionary of entity relationship data schemas is presented. The formal properties of such structuring primitives are investigated, and the feasibility of their usage is shown by providing a methodology for dictionary design.>

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

In this paper we solve, for triconnected digraphs, the problem of the existence of a P-time algorithm for testing if a digraph has an upward drawing, i.e. a drawing such that all the edges point upward.The problem arises in the fields of ordered sets and automatic graph drawing and was open from several years.The time complexity of the proposed algorithm is O(n + r3/ogr), where n is the number of vertices and r is the number of sources and sinks of the digraph.

Given a graph G with n vertices and m edges, a k-connectivity query for vertices v' and v" of G asks whether there exist k disjoint paths between v' and v". The authors consider the problem of performing k-connectivity queries for k>

Article Free Access Share on Area requirement and symmetry display in drawing graphs Authors: G. Di Battista Dipartimento di Informatica e Sistemistica - University of Rome, Via Buonarroti, 12 - 00185 Rome, Italy Dipartimento di Informatica e Sistemistica - University of Rome, Via Buonarroti, 12 - 00185 Rome, ItalyView Profile , R. Tamassia Department of Computer Science - Brown University, Box 1910 - Providence, RI Department of Computer Science - Brown University, Box 1910 - Providence, RIView Profile , I. G. Tollis Department of Computer Science - The University of Texas at Dallas, P.O. Box 830688, MP 3.1- Richardson, TX Department of Computer Science - The University of Texas at Dallas, P.O. Box 830688, MP 3.1- Richardson, TXView Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989 Pages 51–60https://doi.org/10.1145/73833.73839Online:05 June 1989Publication History 22citation409DownloadsMetricsTotal Citations22Total Downloads409Last 12 Months5Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The incremental planarity testing problem consists of performing the following operations on a planar graph G with n vertices: (1) testing whether a new edge can be added to G so that the resulting graph is itself planar; (2) adding vertices and edges such that planarity is preserved. An efficient technique for incremental planarity testing that uses O(n) space and supports tests and insertion of vertices and edges in O(log n) time is presented. The bounds for queries and vertex insertions are worst case, and the bound for edge insertions is amortized.>

In diagrammatic representations of hierarchies the minimization of the number of crossings between edges is a well-known criterion for improving readability. An efficient algorithm for testing if a hierarchy is planar (i.e. if it can be drawn without edge crossings) is proposed. A complete combinatorial characterization of the class of planar hierarchies is also given.>

The state of the art in automatic graph drawing is reviewed, with special attention to the readability of information system diagrams. Existing results in the literature are compared, and a comprehensive algorithmic approach to the problem is proposed. The algorithm presented draws graphs on a grid and is suitable for both undirected graphs and mixed graphs that contain as subgraphs hierarchic structures. Several applications of GIOTTO, a graphic tool that embodies the aforementioned facility, are shown.>