@inproceedings{1381,
  abstract     = {Motivated by Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into double-struck Rd without higher-multiplicity intersections. We focus on conditions for the existence of almost r-embeddings, i.e., maps f : K → double-struck Rd such that f(σ1) ∩ ⋯ ∩ f(σr) = ∅ whenever σ1, ..., σr are pairwise disjoint simplices of K. Generalizing the classical Haefliger-Weber embeddability criterion, we show that a well-known necessary deleted product condition for the existence of almost r-embeddings is sufficient in a suitable r-metastable range of dimensions: If rd ≥ (r + 1) dim K + 3, then there exists an almost r-embedding K → double-struck Rd if and only if there exists an equivariant map (K)Δ r → Sr Sd(r-1)-1, where (K)Δ r is the deleted r-fold product of K, the target Sd(r-1)-1 is the sphere of dimension d(r - 1) - 1, and Sr is the symmetric group. This significantly extends one of the main results of our previous paper (which treated the special case where d = rk and dim K = (r - 1)k for some k ≥ 3), and settles an open question raised there.},
  author       = {Mabillard, Isaac and Wagner, Uli},
  location     = {Medford, MA, USA},
  pages        = {51.1 -- 51.12},
  publisher    = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH},
  title        = {{Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range}},
  doi          = {10.4230/LIPIcs.SoCG.2016.51},
  volume       = {51},
  year         = {2016},
}

@article{1408,
  abstract     = {The concept of well group in a special but important case captures homological properties of the zero set of a continuous map (Formula presented.) on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within (Formula presented.) distance r from f for a given (Formula presented.). The main drawback of the approach is that the computability of well groups was shown only when (Formula presented.) or (Formula presented.). Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of (Formula presented.) by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and (Formula presented.), our approximation of the (Formula presented.)th well group is exact. For the second part, we find examples of maps (Formula presented.) with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.},
  author       = {Franek, Peter and Krcál, Marek},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {126 -- 164},
  publisher    = {Springer},
  title        = {{On computability and triviality of well groups}},
  doi          = {10.1007/s00454-016-9794-2},
  volume       = {56},
  year         = {2016},
}

@article{1411,
  abstract     = {We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M 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 ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai 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 M 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 M 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. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov.},
  author       = {Matoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli},
  journal      = {Israel Journal of Mathematics},
  number       = {1},
  pages        = {37 -- 79},
  publisher    = {Springer},
  title        = {{Untangling two systems of noncrossing curves}},
  doi          = {10.1007/s11856-016-1294-9},
  volume       = {212},
  year         = {2016},
}

@inproceedings{1237,
  abstract     = {Bitmap images of arbitrary dimension may be formally perceived as unions of m-dimensional boxes aligned with respect to a rectangular grid in ℝm. Cohomology and homology groups are well known topological invariants of such sets. Cohomological operations, such as the cup product, provide higher-order algebraic topological invariants, especially important for digital images of dimension higher than 3. If such an operation is determined at the level of simplicial chains [see e.g. González-Díaz, Real, Homology, Homotopy Appl, 2003, 83-93], then it is effectively computable. However, decomposing a cubical complex into a simplicial one deleteriously affects the efficiency of such an approach. In order to avoid this overhead, a direct cubical approach was applied in [Pilarczyk, Real, Adv. Comput. Math., 2015, 253-275] for the cup product in cohomology, and implemented in the ChainCon software package [http://www.pawelpilarczyk.com/chaincon/]. We establish a formula for the Steenrod square operations [see Steenrod, Annals of Mathematics. Second Series, 1947, 290-320] directly at the level of cubical chains, and we prove the correctness of this formula. An implementation of this formula is programmed in C++ within the ChainCon software framework. We provide a few examples and discuss the effectiveness of this approach. One specific application follows from the fact that Steenrod squares yield tests for the topological extension problem: Can a given map A → Sd to a sphere Sd be extended to a given super-complex X of A? In particular, the ROB-SAT problem, which is to decide for a given function f: X → ℝm and a value r > 0 whether every g: X → ℝm with ∥g - f ∥∞ ≤ r has a root, reduces to the extension problem.},
  author       = {Krcál, Marek and Pilarczyk, Pawel},
  location     = {Marseille, France},
  pages        = {140 -- 151},
  publisher    = {Springer},
  title        = {{Computation of cubical Steenrod squares}},
  doi          = {10.1007/978-3-319-39441-1_13},
  volume       = {9667},
  year         = {2016},
}

@article{1282,
  abstract     = {We consider higher-dimensional generalizations of the normalized Laplacian and the adjacency matrix of graphs and study their eigenvalues for the Linial–Meshulam model Xk(n, p) of random k-dimensional simplicial complexes on n vertices. We show that for p = Ω(logn/n), the eigenvalues of each of the matrices are a.a.s. concentrated around two values. The main tool, which goes back to the work of Garland, are arguments that relate the eigenvalues of these matrices to those of graphs that arise as links of (k - 2)-dimensional faces. Garland’s result concerns the Laplacian; we develop an analogous result for the adjacency matrix. The same arguments apply to other models of random complexes which allow for dependencies between the choices of k-dimensional simplices. In the second part of the paper, we apply this to the question of possible higher-dimensional analogues of the discrete Cheeger inequality, which in the classical case of graphs relates the eigenvalues of a graph and its edge expansion. It is very natural to ask whether this generalizes to higher dimensions and, in particular, whether the eigenvalues of the higher-dimensional Laplacian capture the notion of coboundary expansion—a higher-dimensional generalization of edge expansion that arose in recent work of Linial and Meshulam and of Gromov; this question was raised, for instance, by Dotterrer and Kahle. We show that this most straightforward version of a higher-dimensional discrete Cheeger inequality fails, in quite a strong way: For every k ≥ 2 and n ∈ N, there is a k-dimensional complex Yn k on n vertices that has strong spectral expansion properties (all nontrivial eigenvalues of the normalised k-dimensional Laplacian lie in the interval [1−O(1/√1), 1+0(1/√1]) but whose coboundary expansion is bounded from above by O(log n/n) and so tends to zero as n → ∞; moreover, Yn k can be taken to have vanishing integer homology in dimension less than k.},
  author       = {Gundert, Anna and Wagner, Uli},
  journal      = {Israel Journal of Mathematics},
  number       = {2},
  pages        = {545 -- 582},
  publisher    = {Springer},
  title        = {{On eigenvalues of random complexes}},
  doi          = {10.1007/s11856-016-1419-1},
  volume       = {216},
  year         = {2016},
}

@unpublished{8183,
  abstract     = {We study conditions under which a finite simplicial complex $K$ can be mapped to $\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding is a map $f: K\to \mathbb R^d$ such that the images of any $r$
pairwise disjoint simplices of $K$ do not have a common point. We show that if $r$ is not a prime power and $d\geq 2r+1$, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost $r$-embedding of
the $(d+1)(r-1)$-simplex in $\mathbb R^d$. This improves on previous constructions of counterexamples (for $d\geq 3r$) based on a series of papers by M. \"Ozaydin, M. Gromov, P. Blagojevi\'c, F. Frick, G. Ziegler, and the second and fourth present authors. The counterexamples are obtained by proving the following algebraic criterion in codimension 2: If $r\ge3$ and if $K$ is a finite $2(r-1)$-complex then there exists an almost $r$-embedding $K\to \mathbb R^{2r}$ if and only if there exists a general position PL map $f:K\to \mathbb R^{2r}$ such that the algebraic intersection number of the $f$-images of any $r$ pairwise disjoint simplices of $K$ is zero. This result can be restated in terms of cohomological obstructions or equivariant maps, and extends an analogous codimension 3 criterion by the second and fourth authors. As another application we classify ornaments $f:S^3 \sqcup S^3\sqcup S^3\to \mathbb R^5$ up to ornament
concordance. It follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for $r=2$ is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample.},
  author       = {Avvakumov, Sergey and Mabillard, Isaac and Skopenkov, A. and Wagner, Uli},
  booktitle    = {arXiv},
  title        = {{Eliminating higher-multiplicity intersections, III. Codimension 2}},
  year         = {2015},
}

@article{1642,
  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 result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident to at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.},
  author       = {Fulek, Radoslav and Kynčl, Jan and Malinovič, Igor and Pálvölgyi, Dömötör},
  issn         = {1077-8926},
  journal      = {Electronic Journal of Combinatorics},
  number       = {4},
  publisher    = {Electronic Journal of Combinatorics},
  title        = {{Clustered planarity testing revisited}},
  doi          = {10.37236/5002},
  volume       = {22},
  year         = {2015},
}

@article{1682,
  abstract     = {We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f:K→ ℝn on a finite simplicial complex K and α > 0, it holds that each function g: K → ℝn such that ||g - f || ∞ < α, has a root in K. Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed n, assuming dimK ≤ 2n - 3. This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis. Via a reverse reduction, we prove that the problem is undecidable when dim K > 2n - 2, where the threshold comes from the stable range in homotopy theory. For the lucidity of our exposition, we focus on the setting when f is simplexwise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.},
  author       = {Franek, Peter and Krcál, Marek},
  journal      = {Journal of the ACM},
  number       = {4},
  publisher    = {ACM},
  title        = {{Robust satisfiability of systems of equations}},
  doi          = {10.1145/2751524},
  volume       = {62},
  year         = {2015},
}

@inproceedings{1685,
  abstract     = {Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3.
Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest.},
  author       = {Cohen Addad, Vincent and De Mesmay, Arnaud N},
  location     = {Patras, Greece},
  pages        = {386 -- 398},
  publisher    = {Springer},
  title        = {{A fixed parameter tractable approximation scheme for the optimal cut graph of a surface}},
  doi          = {10.1007/978-3-662-48350-3_33},
  volume       = {9294},
  year         = {2015},
}

@article{1688,
  abstract     = {We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant (Formula presented.) such that whenever (Formula presented.) are n-element subsets of (Formula presented.), we can find a point (Formula presented.) and subsets (Formula presented.) for every i∈[d+1], each of size at least cdn, such that p belongs to all rainbowd-simplices determined by (Formula presented.) simplices with one vertex in each Yi. We show a super-exponentially decreasing upper bound (Formula presented.). The ideas used in the proof of the upper bound also help us to prove Pach’s theorem with (Formula presented.), which is a lower bound doubly exponentially decreasing in d (up to some polynomial in the exponent). For comparison, Pach’s original approach yields a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and Suk recently obtained a hypergraph density result implying a proof of Pach’s theorem with (Formula presented.). In our construction for the upper bound, we use the fact that the minimum solid angle of every d-simplex is super-exponentially small. This fact was previously unknown and might be of independent interest. For the lower bound, we improve the ‘separation’ part of the argument by showing that in one of the key steps only d+1 separations are necessary, compared to 2d separations in the original proof. We also provide a measure version of Pach’s theorem.},
  author       = {Karasev, Roman and Kynčl, Jan and Paták, Pavel and Patakova, Zuzana and Tancer, Martin},
  journal      = {Discrete & Computational Geometry},
  number       = {3},
  pages        = {610 -- 636},
  publisher    = {Springer},
  title        = {{Bounds for Pach's selection theorem and for the minimum solid angle in a simplex}},
  doi          = {10.1007/s00454-015-9720-z},
  volume       = {54},
  year         = {2015},
}

@article{1730,
  abstract     = {How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart). Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993), a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions. Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition. Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations.},
  author       = {Colin De Verdière, Éric and Hubard, Alfredo and De Mesmay, Arnaud N},
  journal      = {Discrete & Computational Geometry},
  number       = {3},
  pages        = {587 -- 620},
  publisher    = {Springer},
  title        = {{Discrete systolic inequalities and decompositions of triangulated surfaces}},
  doi          = {10.1007/s00454-015-9679-9},
  volume       = {53},
  year         = {2015},
}

@inproceedings{1510,
  abstract     = {The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status. },
  author       = {Franek, Peter and Krcál, Marek},
  location     = {Eindhoven, Netherlands},
  pages        = {842 -- 856},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{On computability and triviality of well groups}},
  doi          = {10.4230/LIPIcs.SOCG.2015.842},
  volume       = {34},
  year         = {2015},
}

@inproceedings{1511,
  abstract     = {The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.},
  author       = {Goaoc, Xavier and Mabillard, Isaac and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
  location     = {Eindhoven, Netherlands},
  pages        = {476 -- 490},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result}},
  doi          = {10.4230/LIPIcs.SOCG.2015.476},
  volume       = {34 },
  year         = {2015},
}

@inproceedings{1512,
  abstract     = {We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.},
  author       = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
  location     = {Eindhoven, Netherlands},
  pages        = {507 -- 521},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Bounding Helly numbers via Betti numbers}},
  doi          = {10.4230/LIPIcs.SOCG.2015.507},
  volume       = {34},
  year         = {2015},
}

@inproceedings{1595,
  abstract     = {A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, . . . , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing- free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.},
  author       = {Fulek, Radoslav and Pelsmajer, Michael and Schaefer, Marcus},
  location     = {Los Angeles, CA, USA},
  pages        = {99 -- 110},
  publisher    = {Springer},
  title        = {{Hanani-Tutte for radial planarity}},
  doi          = {10.1007/978-3-319-27261-0_9},
  volume       = {9411},
  year         = {2015},
}

@inbook{1596,
  abstract     = {Let C={C1,...,Cn} denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection C forms a visibility clique if for everyi < j the intersection Ci and (Ci ∩ Cj)\⋃i<l<jCl =∅.elements that are stacked between them, i.e., We show that if C forms a visibility clique its size is bounded from above by O(k4) thereby improving the upper bound of 22k from the aforementioned paper. We also obtain an upper bound of 22(k/2)+2 on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gon.},
  author       = {Fulek, Radoslav and Radoičić, Radoš},
  booktitle    = {Graph Drawing and Network Visualization},
  isbn         = {978-3-319-27260-3},
  location     = {Los Angeles, CA, United States},
  pages        = {373 -- 379},
  publisher    = {Springer Nature},
  title        = {{Vertical visibility among parallel polygons in three dimensions}},
  doi          = {10.1007/978-3-319-27261-0_31},
  volume       = {9411},
  year         = {2015},
}

@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},
}

@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},
}

@article{2154,
  abstract     = {A result of Boros and Füredi (d = 2) and of Bárány (arbitrary d) asserts that for every d there exists cd > 0 such that for every n-point set P ⊂ ℝd, some point of ℝd is covered by at least (Formula presented.) of the d-simplices spanned by the points of P. The largest possible value of cd has been the subject of ongoing research. Recently Gromov improved the existing lower bounds considerably by introducing a new, topological proof method. We provide an exposition of the combinatorial component of Gromov's approach, in terms accessible to combinatorialists and discrete geometers, and we investigate the limits of his method. In particular, we give tighter bounds on the cofilling profiles for the (n - 1)-simplex. These bounds yield a minor improvement over Gromov's lower bounds on cd for large d, but they also show that the room for further improvement through the cofilling profiles alone is quite small. We also prove a slightly better lower bound for c3 by an approach using an additional structure besides the cofilling profiles. We formulate a combinatorial extremal problem whose solution might perhaps lead to a tight lower bound for cd.},
  author       = {Matoušek, Jiří and Wagner, Uli},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {1 -- 33},
  publisher    = {Springer},
  title        = {{On Gromov's method of selecting heavily covered points}},
  doi          = {10.1007/s00454-014-9584-7},
  volume       = {52},
  year         = {2014},
}

@inproceedings{2157,
  abstract     = {We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in ℝ3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, i.e., an essential curve in the boundary of X bounding a disk in S3 nX with length bounded by a computable function of the number of tetrahedra of X.},
  author       = {Matoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli},
  booktitle    = {Proceedings of the Annual Symposium on Computational Geometry},
  location     = {Kyoto, Japan},
  pages        = {78 -- 84},
  publisher    = {ACM},
  title        = {{Embeddability in the 3 sphere is decidable}},
  doi          = {10.1145/2582112.2582137},
  year         = {2014},
}