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

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