Session 1 
08:5509:00 
Opening:
Emo Welzl 
09:0009:18 
Winning fast in biased MakerBreaker games
Miloš Stojaković, University of Novi Sad
(Gremo May 15, 2002  Sept 30, 2005)
Abstract:
We take a look at two standard MakerBreaker 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:1809:36 
Compatible connectivityaugmentation of planar disconnected graphs
Luis F. Barba, UL Bruxelles and Carleton University
Abstract:
Motivated by applications to graph morphing, we consider the
following compatible connectivityaugmentation problem: We are
given a labeled nvertex planar graph G, that has
r>1 connected components, and k>1 isomorphic planar
straightline drawings G_{1},...,G_{k}, 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 G_{1},...,G_{k} as points and
straightline segments, respectively, to obtain k planar
straightline drawings isomorphic to the augmentation of
G. We show that adding Θ(nr^{11/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:3609:54 
Solving generalized Laplacian linear systems
Sebastian Stich, UC de Louvain
(Gremo Sep 15, 2010  Sep 30, 2014)
Abstract:
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 unitcost RAM model.
Motivated by an engineering application, we recently considered
linear systems where L does not describe a graph, but a
higherdimensional 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:5410:12 
On tangencies between algebraic curves
József Solymosi, University of British Columbia
(Gremo Jan 1, 2000  Mar 31, 2001)
Abstract:
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 R^{2} or C^{2}, there
are O(n^{3/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(n^{3/2}) curvecurve tangencies.
Joint work with Josh Zahl.

10:1210:42 
Coffee Break 
Session 2 
10:4211:00 
Vertical visibility among parallel polygons in three dimensions
Radoslav Fulek, IST Austria
Abstract:
Let C be a collection of homothetic copies of a convex kgon 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 2^{2{k \choose 2}+2} on the size of
a visibility clique of homothetic copies of a convex kgon. In the
case of translates of a regular convex kgon we improve the bound
to O(k^{4}).
Joint work (in progress) with Radoš Radoičić.

11:0011:18 
Choosing representatives for moving points
Shakhar Smorodinsky, Ben Gurion University and EPFL
(Gremo Feb 15, 2004  Oct 31, 2004)
Abstract:
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 xaxis.

11:1811:36 
Cartesian products in Erdős geometry
Frank de Zeeuw, EPF Lausanne
Abstract:
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 SchwartzZippel
lemma, an algebraic surface F(x,y,z)=0 in R^{3} 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 ElekesSzabó theorem, which can provide highly nontrivial
bounds in Erdőstype questions, for example about distances or
collinearity. I will discuss this theorem, a few of its
applications, and some recent variants.

11:3611:54 
Covering inscribed polytopes by their smaller copies
Márton Naszódi, EPF Lausanne
Abstract:
We can define the illumination number of a convex body in
Euclidean dspace 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
threedimensional case is already open, and  I think 
interesting.

11:5412:12 
Constructing plane graphs in simple topological graphs
Andres RuizVargas, EPF Lausanne
Abstract:
We show a simple way to construct plane subgraphs of minimum
degree two in simple topological graphs.

12:1212:15 
Organizational Remarks:
Michael Hoffmann 