Thursday, March 15, 2012: Jeff Erickson (U. of Illinois at Urbana-Champaign, USA, and IST, Vienna, Austria) and Arnaud de Mesmay (ENS, Paris)

UNUSUAL ROOM: Room Pasteur. Enter the 45, rue d'Ulm through the lodge, then go immediately to your right. Enter the door labeled "Pavillon Pasteur", in the Philosophy Department, walk in the corridor, find the stairs to your right, go one level up.

At 2pm: Jeff Erickson, Topological hexahedral meshing of multiply-connected domains

In the mid-1990s, Thurston and Mitchell proved that any quadrilateral mesh of the sphere with an even number of faces can be extended to a topological hexahedral mesh of the ball. I will prove the following natural generalization of Thurston and Mitchell's result to higher-genus surfaces, which surprisingly seems to be new. A quadrilateral mesh of any closed surface embedded in R^3 can be extended to a compatible hexahedral mesh of the interior if and only if (1) the surface mesh has an even number of faces, and (2) the system of curves dual to the surface mesh has trivial Z_2-homology in the interior body.

Around 3:15pm: Arnaud de Mesmay, Testing graph isotopy on surfaces

In the study of graphs embedded on surfaces, the notion of graph isotopy is a natural variation of the well known homotopy of paths or cycles: We say that two graphs are isotopic if there exists a continous deformation between them. In this work, we investigate the following problem : Given two embeddings of the same abstract graph on a surface, decide whether they are isotopic.

We provide efficient algorithms to solve this problem in two models. In the first one the embeddings are described by their arrangements with a cellularly embedded graph on the surface; in the second one they are piecewise-linear embeddings in the plane minus a finite set of points. The main tools we use are the existing algorithms to test homotopy, which we use as a subroutine, and a surgical approach inspired by the theory of mapping class groups. As a by-product, we reprove the following mathematical characterization, first observed by Ladegaillerie: Two graph embeddings are isotopic if and only if they are homotopic and congruent by an oriented homeomorphism.

This is joint work with Éric Colin de Verdière, to appear at SoCG 2012.

Thursday, January 5, 2012: Thomas Sauerwald (MPI Saarbrücken, Germany)

Ultra-Fast Rumor Spreading on Social Networks

11am, at ENS, 45 rue d'Ulm, room U/V (Aile Rataud, 2nd basement floor, see map).

We analyze the popular push-pull protocol for spreading rumors in networks. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on random graphs that have a power law degree distribution with an arbitrary exponent beta > 2.

Our main findings reveal a dichotomy in the performance of the protocol that depends on the exponent of the power law. More specifically, we show that if 2 < beta < 3, then the rumor spreads to almost all nodes in Theta(log log n) rounds with high probability. This is exponentially faster than all previously known upper bounds for the push-pull protocol established for various classes of networks. On the other hand, if beta > 3, then Omega(log n) rounds are necessary.

This is joint work with Nikolaos Fountoulakis and Konstantinos Panagiotou.

Tuesday, December 13, 2011: Menelaos Karavelas (U. of Crete, Greece)

The maximum number of faces of the Minkowski sum of two convex polytopes

2pm, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor).

Abstract: We derive tight expressions for the maximum values of the number of $k$-faces, $0\le k\le d-1$, of the Minkowski sum $P_1\oplus P_2$ of two $d$-dimensional convex polytopes $P_1$ and $P_2$, as a function of the number of vertices of the polytopes.

For even dimensions $d\ge 2$, the maximum values are attained if $P_1$ and $P_2$ are cyclic $d$-polytopes with disjoint vertex sets. For odd dimensions $d\ge 3$, the maximum values are attained if $P_1$ and $P_2$ are $\lfloor d/2\rfloor$-neighborly $d$-polytopes, whose vertex sets are chosen appropriately from two distinct $d$-dimensional moment-like curves.

This is joint work with Eleni Tzanaki.

References:

• arXiv report: http://www.arxiv.org/abs/1106.6254
• SODA 2012 preprint: http://www.tem.uoc.gr/~mkaravel/papers/mnfms-soda12.pdf

Thursday, October 20, 2011: Jeff Erickson (U. of Illinois at Urbana-Champaign, USA, and IST, Vienna, Austria)

Tracing Curves on Triangulated Surfaces

at 2pm, at ENS, 45 rue d'Ulm, salle des Hauts du DI. Access modified: Enter the main building through the main entrance; in the hall ("Aquarium"), take the staircase on the left ("Headmistress' staircase"), 3rd floor, door to the right.

Abstract: Let S be a triangulated surface, possibly with boundary, composed of n triangles. A simple path or cycle in S is normal if it avoids every vertex of S and it does not cross any edge of S twice in a row. We describe a simple algorithm to trace any normal curve in S in O(n^2\log X) time, where X is the total number of times the curve crosses edges of S. In particular, our algorithm runs in polynomial time even when the number of crossings is exponential in n. Our tracing algorithm computes a new cellular decomposition of S with complexity O(n); the traced curve appears as a simple path or cycle in the 1-skeleton of the new decomposition.

Our tracing strategy implies several fast algorithms for (multi)curves represented by normal coordinates. For example, we can count the components of a normal curve, determine whether two disjoint normal curves are isotopic, or determine whether a normal curve disconnects two given points on the surface, all in O(n^2\log X) time. Our algorithms are competitive with and conceptually simpler than earlier algorithms by Schaefer, Sedgwick, and Stefankovic [COCOON 2002] based on word equations and text compression.

Our algorithm can also be used to trace simple geodesic paths in piecewise-linear surfaces, represented by a set of Euclidean triangles with pairs of equal-length edges identified. For example, given a starting point and a direction, in the local coordinate system of one of the triangles, we can locate the first point of self-intersection of the resulting geodesic path in O(n^2\log X) time.

This is unpublished joint work with my PhD student Amir Nayyeri. The talk will be self-contained; no prior exposure to computational topology is necessary.

Thursday, June 16, 2011: Benjamin A. Burton (U. Queensland, Brisbane, Australia)

Unknot recognition, linear programming and the elusive polynomial time algorithm

at 11am, at ENS, 45 rue d'Ulm, salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor)

Abstract: What do practical tools such as integer and linear programming have to do with theoretical problems such as unknot recognition and the Poincaré conjecture? In this talk we explore new approaches to old and difficult computational problems from geometry and topology: how to tell whether a loop of string is knotted, or whether a 3-dimensional space has no interesting topological features. Although the best known algorithms for these problems run in exponential time, there is increasing evidence that a polynomial time solution might be possible. We outline several promising approaches in which linear programming and integer programming play a starring role.

Slides of the talk.