@inproceedings{10793,
  abstract     = {The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this classical result to clustered graphs with two disjoint clusters, and show that a straightforward extension of our result to flat clustered graphs with three or more disjoint clusters is not possible.

We also give a new and short proof for a related result by Di Battista and Frati based on the matroid intersection algorithm.},
  author       = {Fulek, Radoslav and Kynčl, Jan and Malinović, Igor and Pálvölgyi, Dömötör},
  booktitle    = {International Symposium on Graph Drawing},
  issn         = {0302-9743},
  pages        = {428--436},
  publisher    = {Springer Nature},
  title        = {{Clustered planarity testing revisited}},
  doi          = {10.1007/978-3-662-45803-7_36},
  volume       = {8871},
  year         = {2014},
}

@techreport{7038,
  author       = {Huszár, Kristóf and Rolinek, Michal},
  pages        = {5},
  publisher    = {IST Austria},
  title        = {{Playful Math - An introduction to mathematical games}},
  year         = {2014},
}

@article{1842,
  abstract     = {We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n3) and O(n10), in the convex and general case, respectively. We then apply similar methods to prove an (Formula presented.) upper bound on the Ramsey number of a path with n ordered vertices.},
  author       = {Cibulka, Josef and Gao, Pu and Krcál, Marek and Valla, Tomáš and Valtr, Pavel},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {64 -- 79},
  publisher    = {Springer},
  title        = {{On the geometric ramsey number of outerplanar graphs}},
  doi          = {10.1007/s00454-014-9646-x},
  volume       = {53},
  year         = {2014},
}

@inproceedings{2159,
  abstract     = {Motivated by topological Tverberg-type problems, we consider multiple (double, triple, and higher multiplicity) selfintersection points of maps from finite simplicial complexes (compact polyhedra) into ℝd and study conditions under which such multiple points can be eliminated. The most classical case is that of embeddings (i.e., maps without double points) of a κ-dimensional complex K into ℝ2κ. For this problem, the work of van Kampen, Shapiro, and Wu provides an efficiently testable necessary condition for embeddability (namely, vanishing of the van Kampen ob-struction). For κ ≥ 3, the condition is also sufficient, and yields a polynomial-time algorithm for deciding embeddability: One starts with an arbitrary map f : K→ℝ2κ, which generically has finitely many double points; if k ≥ 3 and if the obstruction vanishes then one can successively remove these double points by local modifications of the map f. One of the main tools is the famous Whitney trick that permits eliminating pairs of double points of opposite intersection sign. We are interested in generalizing this approach to intersection points of higher multiplicity. We call a point y 2 ℝd an r-fold Tverberg point of a map f : Kκ →ℝd if y lies in the intersection f(σ1)∩. ∩f(σr) of the images of r pairwise disjoint simplices of K. The analogue of (non-)embeddability that we study is the problem Tverbergκ r→d: Given a κ-dimensional complex K, does it satisfy a Tverberg-type theorem with parameters r and d, i.e., does every map f : K κ → ℝd have an r-fold Tverberg point? Here, we show that for fixed r, κ and d of the form d = rm and k = (r-1)m, m ≥ 3, there is a polynomial-time algorithm for deciding this (based on the vanishing of a cohomological obstruction, as in the case of embeddings). Our main tool is an r-fold analogue of the Whitney trick: Given r pairwise disjoint simplices of K such that the intersection of their images contains two r-fold Tverberg points y+ and y- of opposite intersection sign, we can eliminate y+ and y- by a local isotopy of f. In a subsequent paper, we plan to develop this further and present a generalization of the classical Haeiger-Weber Theorem (which yields a necessary and sufficient condition for embeddability of κ-complexes into ℝd for a wider range of dimensions) to intersection points of higher multiplicity.},
  author       = {Mabillard, Isaac and Wagner, Uli},
  booktitle    = {Proceedings of the Annual Symposium on Computational Geometry},
  location     = {Kyoto, Japan},
  pages        = {171 -- 180},
  publisher    = {ACM},
  title        = {{Eliminating Tverberg points, I. An analogue of the Whitney trick}},
  doi          = {10.1145/2582112.2582134},
  year         = {2014},
}

@inproceedings{2244,
  abstract     = {We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a compact two-dimensional surface ℳ with boundary. Each αi and each βj is either an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere with h ≥ 0 boundary components ("holes"), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. },
  author       = {Matoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli},
  location     = {Bordeaux, France},
  pages        = {472 -- 483},
  publisher    = {Springer},
  title        = {{Untangling two systems of noncrossing curves}},
  doi          = {10.1007/978-3-319-03841-4_41},
  volume       = {8242},
  year         = {2013},
}

@inproceedings{2807,
  abstract     = {We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X; Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected; informally, this means that Y has \no holes up to dimension k-1" (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation). This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where Y is a cell complex with certain rather compact encoding. We strengthen his result to #P-hardness for Y given as a simplicial complex. },
  author       = {Čadek, Martin and Krcál, Marek and Matoušek, Jiří and Vokřínek, Lukáš and Wagner, Uli},
  booktitle    = {45th Annual ACM Symposium on theory of computing},
  location     = {Palo Alto, CA, United States},
  pages        = {595 -- 604},
  publisher    = {ACM},
  title        = {{Extending continuous maps: Polynomiality and undecidability}},
  doi          = {10.1145/2488608.2488683},
  year         = {2013},
}