Part of the joint STOC/SoCG 2016 workshop day
Date:
June 18th, 2016
Location:
Hyatt Regency in Cambridge
Organizers:
Kenichi Kawarabayashi and
Anastasios Sidiropoulos
The workshop will focus on recent algorithmic advancements on problems on topologically restricted graphs, such as planar, surfaceembedded, small treewidth, minorfree graphs, and graphs of small crossing number. The goal will be to emphasize developments that are of importance in the areas of fixed parameter tractability, approximation algorithms, topological graph theory, and metric embeddings. The program will attempt to highlight developments that are of importance in all of these areas, and emphasize technical connections between them.
Chandra Chekuri, University of Illinois at UrbanaChampaign (the talk by Chandra Chekuri has been cancelled)
Éric Colin de Verdière, École Normale Supérieure (Paris)
Petr Hliněný, Masaryk University
Philip Klein, Brown University
Robert Krauthgamer, Weizmann Institute of Science
Daniel Lokshtanov, University of Bergen
Amir Nayyeri, Oregon State University
Morning session
9:00am  9:30am  Petr Hliněný, Masaryk University 
Title:
Toroidal Grid Minors, Embedding Stretch, and Crossing Number Abstract: We introduce a new embedding density parameter for graphs embedded on orientable surfaces, called the stretch, and approximately relate this parameter to the size of the largest possible (and nontrivial) toroidal grid which is a minor of the graph. The approximation bounds depend only on the genus and the maximum degree. We show how to efficiently compute the stretch of a given embedding and how the stretch relates to the (planar) crossing number of the embedded graph. This talk is based on joint work with S. Cabello, M. Chimani and G. Salazar. 

9:35am  10:05am  Daniel Lokshtanov, University of Bergen 
Title:
Subexponential parameterized algorithms for planar and apexminorfree graphs via low treewidth pattern covering Abstract: We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties:
Based on a joint work with Fedor V. Fomin, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh 

10:10am  10:40am  Amir Nayyeri, Oregon State University 
Title:
Minimum cuts on surface embedded graphs Abstract: The algorithmic problem of computing minimum cuts in graphs has been the focus of many studies in the past few decades. In planar graphs, nearly linear time algorithms has been discovered for computing an stminimum cut, a global minimum cut, and the GomoryHu tree (that represents all minimum cuts). All these algorithms rely heavily on the fact that in planar graphs the dual of a cut is a cycle. Generalizing these algorithm has been challenging as this duality cease to exist in surfaces of positive genus. In this talk, I will describe algorithms for computing minimum cuts on genus g surfaces. The running time of all these algorithm are of the form $O(f(g)n\text{polylog} n)$. The key insight is computing short cycles in all homology classes and combining them to construct the dual of the minimum cut. I describe ideas for computing minimum homologous cycles and assembling them. I will explain methods from three different papers that are results of joint work with Glencora Borradaile, Jeff Erickson, David Eppstein, Kyle Fox, Christian WulffNilsen. 
Afternoon session
3:30pm  4:00pm  Éric Colin de Verdière, École Normale Supérieure (Paris) 
Title:
Multicuts in planar and boundedgenus graphs with bounded number of terminals Abstract: Given an undirected, edgeweighted graph $G$ together with pairs of vertices, called pairs of terminals, the minimum multicut problem asks for a minimumweight set of edges such that, after deleting these edges, the two terminals of each pair belong to different connected components of the graph. Relying on topological techniques, we provide a polynomialtime algorithm for this problem in the case where $G$ is embedded on a fixed surface of genus $g$ (e.g., when $G$ is planar) and has a fixed number $t$ of terminals. The running time is a polynomial of degree $O\big(\sqrt{g^2+gt}\big)$ in the input size. In the planar case, our result corrects an error in an extended abstract by Bentz [Int. Workshop on Parameterized and Exact Computation, 109119, 2012]. The minimum multicut problem is also a generalization of the multiway cut problem, a.k.a. multiterminal cut problem; even for this special case, no dedicated algorithm was known for graphs embedded on surfaces. 

4:05pm  4:35pm  Robert Krauthgamer, Weizmann Institute of Science 
Title:
Cutting corners cheaply, or how to remove Steiner points Abstract: I will show how the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which answers a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, for every edgeweighted graph $G=(V,E,w)$ and a subset of terminals $T\subset V$, there is a graph only on the terminals, denoted $G'=(T,E',w')$, which is a minor of $G$ and the shortestpath distance between any two terminals is approximately equal in $G'$ and in $G$, namely within factor $O(\log^5 T)$. Our existence proof is constructive and gives a randomized polynomialtime algorithm. Joint work with Lior Kamma and Huy L. Nguyen 

4:40pm  5:20pm  Philip Klein, Brown University 
Title:
Approximation Schemes for Planar Graphs: A Survey of Methods Abstract: In addressing an NPhard problem in combinatorial optimization, one way to cope is to use an approximation scheme, an algorithm that, for any given $\epsilon>0$, produces a solution whose value is within a $1+\epsilon$ factor of optimal. For many problems on graphs, obtaining such accurate approximations is NPhard if the input is allowed to be any graph but is tractable if the input graph is required to be planar. Research on polynomialtime approximation schemes for optimization problems in planar graphs goes back to the pioneering work of Lipton and Tarjan (1977) and Baker (1983). Since then, however, the scope of problems amenable to approximation has broadened considerably. In this talk I will outline some of the approaches used, especially those that have led to recent results. 
