Martedì 19 maggio – Arc diagrams, flip distances, and Hamiltonian triangulations

=== When ===

Tuesday May 19th at 12:00

 

=== Where ===

Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

 

=== Title ===

Arc diagrams, flip distances, and Hamiltonian triangulations

 

=== Speaker ===

Dr. Michael Hoffmann, ETH Zürich
http://www.inf.ethz.ch/personal/hoffmann/

 

=== Abstract ===

A flip is a local operation on a triangulation (maximal planar graph) that switches the diagonal of a 4-cycle. The flip graph is a graph whose vertices are all triangulations on n vertices and two triangulations are adjacent if they differ by exactly one flip. These graphs have been studied in various settings and have proven to be a very useful and versatile tool to analyze the structure of triangulations, both combinatorially and algorithmically.

In this talk I will present recently improved bounds concerning the combinatorial flip graph, where triangulations are considered to be abstract graphs (rather than, for instance, geometric realizations on a concrete point set). Specifically we show that from every triangulation on n>=6 vertices we can reach a Hamiltonian triangulation by a sequence of less than n/2 flips. An interesting bit about this bound is that it was known that 3n/5-c flips are always sufficient and sometimes necessary to reach a 4-connected triangulation (which by Tutte’s/Whitney’s Theorem is Hamiltonian). As a byproduct we improve the upper bound on the diameter of the flip graph from ~5.2n to ~5n. Finally, I will discuss an application of our result to a graph drawing problem, showing that every planar graph on n vertices admits an arc diagram with less than n/2 biarcs, that is, after subdividing less than n/2 (of potentially 3n-6) edges the resulting graph admits a 2-page book embedding.

(joint work with Jean Cardinal, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein)

Venerdì 8 MAGGIO – Rethinking Virtual Private Networks in the Software-Defined Era

=== When ===

Friday May 8th at 9:00

=== Where ===

Department of Engineering Section of Computer Science and Automation

Via della Vasca Navale, 79

Meeting room (1.10) on 1st floor

=== Title ===

Rethinking Virtual Private Networks in the Software-Defined Era

=== Speaker ===

Gabriele Lospoto PhD Student in Computer Science and Automation Roma Tre University http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=gabriele

=== Abstract ===

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. Joint work with M. Rimondini, B. G. Vignoli, and G. Di Battista The paper will be presented at the forthcoming IEEE IM 2015 (http://im2015.ieee-im.org/)