# Monday May 18th – Planarity of Streamed Graphs

=== When ===

Monday May 18th at 11:00

=== Where ===

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

=== Title ===

Planarity of Streamed Graphs

=== Speaker ===

Giordano Da Lozzo
http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=giordano

=== Abstract ===

Abstract.  In this work we introduce a notion of planarity for graphs that are presented in a streaming fashion.  A streamed graph is a stream of edges $e_1,e_2,…,e_m$ on a vertex set $V$.  A streamed graph is $\omega$-stream planar with respect to a positive integer window size $\omega$ if there exists a sequence of planar topological drawings $\Gamma_i$ of the graphs $G_i=(V,\{e_j \mid i\leq j < i+\omega\})$ such that the common graph  $G^{i}_\cap=G_i\cap G_{i+1}$ is drawn the same in $\Gamma_i$ and in $\Gamma_{i+1}$, for $1\leq i < m-\omega$. The Streamed Planarity Problem with window size $\omega$ asks whether a given streamed graph is $\omega$-streamed planar. We also consider a generalization, where there is an additional backbone graph whose edges have to be present during each time step.
These problems are related to several well-studied planarity problems.

We show that the Streamed Planarity Problem is NP-complete even when the window size is a constant and that the variant with a backbone graph is NP-complete for all $\omega \ge 2$.  On the positive side, we provide $O(n+\omega{}m)$-time algorithms for (i) the case $\omega = 1$ and (ii) all values of $\omega$ provided the backbone graph consists of one $2$-connected component plus isolated vertices and no stream edge connects two isolated vertices. Our results improve on the Hanani-Tutte-style $O((nm)^3)$-time algorithm proposed by Schaefer~[GD’14] for $\omega=1$.

Joint work with Ignaz Rutter.
This work will be presented at CIAC ’15, the 9th International Conference on Algorithms and Complexity, May 20-22, 2015 Paris, France.

# Tuesday May 19th – 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

# 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/)