Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Program — Combinatorial Algorithms Day 2015

8th Combinatorial Algorithms Day

Monday, June 1st 2015

Both sessions are in CAB G51 (the usual Mittagsseminar room).
Here is a PDF-map of ETH Zentrum.

Session 1

08:55-09:00 Opening: Emo Welzl
09:00-09:18 Winning fast in biased Maker-Breaker games
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002 - Sept 30, 2005)

We take a look at two standard Maker-Breaker games played on the complete graph - the Perfect Matching game and the Hamiltonicity game. Our goal is to find out how fast can Maker win the (1:b) biased game, for values of b for which we know that the game is a Maker's win.
Joint work with Asaf Ferber, Dan Hefetz and Mirjana Mikalački.

09:18-09:36 Compatible connectivity-augmentation of planar disconnected graphs
Luis F. Barba, UL Bruxelles and Carleton University

Motivated by applications to graph morphing, we consider the following compatible connectivity-augmentation problem: We are given a labeled n-vertex planar graph G, that has r>1 connected components, and k>1 isomorphic planar straight-line drawings G1,...,Gk, of G. We wish to augment G by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to the k drawings G1,...,Gk as points and straight-line segments, respectively, to obtain k planar straight-line drawings isomorphic to the augmentation of G. We show that adding Θ(nr1-1/k) edges and vertices to G is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all r ∈ {2,...,n} and k>=2. The lower bound holds for all r ∈ {2,...,n/3} and k>=2.

09:36-09:54 Solving generalized Laplacian linear systems
Sebastian Stich, UC de Louvain
(Gremo Sep 15, 2010 - Sep 30, 2014)

A Laplacian linear system is an equation of the form Lx = b, where L describes the Laplacian matrix of a graph G. In 2013, Kelner et al. presented a simple, combinatorial algorithm to solve such systems approximately in nearly linear time. Their algorithm is not only very simple, it was in 2013 also the fastest algorithm in the unit-cost RAM model. Motivated by an engineering application, we recently considered linear systems where L does not describe a graph, but a higher-dimensional simplicial complex. To some extent, the ideas of Kelner et al. can still be applied in this setting. In this talk, I will present the algorithm of Kelner et al. and its generalization to higher dimensions, together with some preliminary results.
Joint work with François Glineur, Guoyong Gu, and Yurii Nesterov.

09:54-10:12 On tangencies between algebraic curves
József Solymosi, University of British Columbia
(Gremo Jan 1, 2000 - Mar 31, 2001)

This talk is about a recent bound for the number of tangencies amongst a family of n algebraic curves in the plane. Given a collection of n bounded degree algebraic curves in R2 or C2, there are O(n3/2) points where two or more curves are tangent. In particular, if no three curves are mutually tangent at a common point, then there are O(n3/2) curve-curve tangencies.
Joint work with Josh Zahl.

10:12-10:42 Coffee Break

Session 2

10:42-11:00 Vertical visibility among parallel polygons in three dimensions
Radoslav Fulek, IST Austria

Let C be a collection of homothetic copies of a convex k-gon P in the plane with given stacking order. The collection C forms a visibility clique if, for every pair of copies P1 and P2 in C, the intersection of P1 and P2 is not covered by the union of the copies in C appearing between P1 and P2 in the stacking order. We obtain an upper bound of 22{k \choose 2}+2 on the size of a visibility clique of homothetic copies of a convex k-gon. In the case of translates of a regular convex k-gon we improve the bound to O(k4).
Joint work (in progress) with Radoš Radoičić.

11:00-11:18 Choosing representatives for moving points
Shakhar Smorodinsky, Ben Gurion University and EPFL
(Gremo Feb 15, 2004 - Oct 31, 2004)

Let P be a set of n moving points in the plane. Namely, the coordinate of each point is a polynomial (in time) of some bounded constant degree. We show that for any k, we can choose a subset N ⊂ P of size O(k log k) such that the Voronoi cells of the points of N at any time t are balanced in the following sense: the Voronoi cell of any point of N in the Voronoi diagram of N at time t contains at most O(n/k) points of P. This bound is nearly tight even when all the points are moving with constant speed on the x-axis.

11:18-11:36 Cartesian products in Erdős geometry
Frank de Zeeuw, EPF Lausanne

A number of interesting problems from combinatorial geometry can be described in terms of the intersection of an algebraic variety with a Cartesian product. For instance, by the Schwartz-Zippel lemma, an algebraic surface F(x,y,z)=0 in R3 intersects a finite product AxAxA in at most deg(F) |A|2 points, and this bound is tight. However, if F does not have a certain special form, one can significantly improve this bound. This is the Elekes-Szabó theorem, which can provide highly nontrivial bounds in Erdős-type questions, for example about distances or collinearity. I will discuss this theorem, a few of its applications, and some recent variants.

11:36-11:54 Covering inscribed polytopes by their smaller copies
Márton Naszódi, EPF Lausanne

We can define the illumination number of a convex body in Euclidean d-space as the minimum number of its positive homothets, with homothety ratio less than one, that cover the body. The general problem of establishing the largest illumination number for a given dimension seems very hard. I am proposing to consider polytopes all of whose vertices lie on a sphere. The three-dimensional case is already open, and - I think - interesting.

11:54-12:12 Constructing plane graphs in simple topological graphs
Andres Ruiz-Vargas, EPF Lausanne

We show a simple way to construct plane subgraphs of minimum degree two in simple topological graphs.

12:12-12:15 Organizational Remarks: Michael Hoffmann

Valid HTML 4.01!