@inproceedings{7990, abstract = {Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).}, author = {Wagner, Uli and Welzl, Emo}, booktitle = {36th International Symposium on Computational Geometry}, isbn = {9783959771436}, issn = {18688969}, location = {Zürich, Switzerland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)}}, doi = {10.4230/LIPIcs.SoCG.2020.67}, volume = {164}, year = {2020}, } @inproceedings{7991, abstract = {We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.}, author = {Avvakumov, Sergey and Nivasch, Gabriel}, booktitle = {36th International Symposium on Computational Geometry}, isbn = {9783959771436}, issn = {18688969}, location = {Zürich, Switzerland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Homotopic curve shortening and the affine curve-shortening flow}}, doi = {10.4230/LIPIcs.SoCG.2020.12}, volume = {164}, year = {2020}, } @inproceedings{7992, abstract = {Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.}, author = {Patakova, Zuzana and Tancer, Martin and Wagner, Uli}, booktitle = {36th International Symposium on Computational Geometry}, isbn = {9783959771436}, issn = {18688969}, location = {Zürich, Switzerland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Barycentric cuts through a convex body}}, doi = {10.4230/LIPIcs.SoCG.2020.62}, volume = {164}, year = {2020}, } @inproceedings{7994, abstract = {In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.}, author = {Arroyo Guevara, Alan M and Bensmail, Julien and Bruce Richter, R.}, booktitle = {36th International Symposium on Computational Geometry}, isbn = {9783959771436}, issn = {18688969}, location = {Zürich, Switzerland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Extending drawings of graphs to arrangements of pseudolines}}, doi = {10.4230/LIPIcs.SoCG.2020.9}, volume = {164}, year = {2020}, } @phdthesis{8032, abstract = {Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.” In this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus.}, author = {Huszár, Kristóf}, isbn = {978-3-99078-006-0}, issn = {2663-337X}, pages = {xviii+120}, publisher = {Institute of Science and Technology Austria}, title = {{Combinatorial width parameters for 3-dimensional manifolds}}, doi = {10.15479/AT:ISTA:8032}, year = {2020}, } @phdthesis{8156, abstract = {We present solutions to several problems originating from geometry and discrete mathematics: existence of equipartitions, maps without Tverberg multiple points, and inscribing quadrilaterals. Equivariant obstruction theory is the natural topological approach to these type of questions. However, for the specific problems we consider it had yielded only partial or no results. We get our results by complementing equivariant obstruction theory with other techniques from topology and geometry.}, author = {Avvakumov, Sergey}, issn = {2663-337X}, pages = {119}, publisher = {Institute of Science and Technology Austria}, title = {{Topological methods in geometry and discrete mathematics}}, doi = {10.15479/AT:ISTA:8156}, year = {2020}, } @inproceedings{8732, abstract = {A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ , it can be decided in polynomial time whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles.}, author = {Arroyo Guevara, Alan M and Klute, Fabian and Parada, Irene and Seidel, Raimund and Vogtenhuber, Birgit and Wiedera, Tilo}, booktitle = {Graph-Theoretic Concepts in Computer Science}, isbn = {9783030604394}, issn = {1611-3349}, location = {Leeds, United Kingdom}, pages = {325--338}, publisher = {Springer Nature}, title = {{Inserting one edge into a simple drawing is hard}}, doi = {10.1007/978-3-030-60440-0_26}, volume = {12301}, year = {2020}, } @article{6563, abstract = {This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps 𝑓,𝑔:𝑋→𝑌, and the second computes the group [𝛴𝑋,𝑌]∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to 𝐴⊆𝑋.}, author = {Filakovský, Marek and Vokřínek, Lukas}, issn = {16153383}, journal = {Foundations of Computational Mathematics}, pages = {311--330}, publisher = {Springer Nature}, title = {{Are two given maps homotopic? An algorithmic viewpoint}}, doi = {10.1007/s10208-019-09419-x}, volume = {20}, year = {2020}, } @inproceedings{15082, abstract = {Two plane drawings of geometric graphs on the same set of points are called disjoint compatible if their union is plane and they do not have an edge in common. For a given set S of 2n points two plane drawings of perfect matchings M1 and M2 (which do not need to be disjoint nor compatible) are disjoint tree-compatible if there exists a plane drawing of a spanning tree T on S which is disjoint compatible to both M1 and M2. We show that the graph of all disjoint tree-compatible perfect geometric matchings on 2n points in convex position is connected if and only if 2n ≥ 10. Moreover, in that case the diameter of this graph is either 4 or 5, independent of n.}, author = {Aichholzer, Oswin and Obmann, Julia and Patak, Pavel and Perz, Daniel and Tkadlec, Josef}, booktitle = {36th European Workshop on Computational Geometry}, location = {Würzburg, Germany, Virtual}, title = {{Disjoint tree-compatible plane perfect matchings}}, year = {2020}, } @article{9308, author = {Avvakumov, Sergey and Wagner, Uli and Mabillard, Isaac and Skopenkov, A. B.}, issn = {0036-0279}, journal = {Russian Mathematical Surveys}, number = {6}, pages = {1156--1158}, publisher = {IOP Publishing}, title = {{Eliminating higher-multiplicity intersections, III. Codimension 2}}, doi = {10.1070/RM9943}, volume = {75}, year = {2020}, } @unpublished{7950, abstract = {The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.}, author = {Biniaz, Ahmad and Jain, Kshitij and Lubiw, Anna and Masárová, Zuzana and Miltzow, Tillmann and Mondal, Debajyoti and Naredla, Anurag Murty and Tkadlec, Josef and Turcotte, Alexi}, booktitle = {arXiv}, title = {{Token swapping on trees}}, year = {2019}, } @unpublished{8182, abstract = {Suppose that $n\neq p^k$ and $n\neq 2p^k$ for all $k$ and all primes $p$. We prove that for any Hausdorff compactum $X$ with a free action of the symmetric group $\mathfrak S_n$ there exists an $\mathfrak S_n$-equivariant map $X \to {\mathbb R}^n$ whose image avoids the diagonal $\{(x,x\dots,x)\in {\mathbb R}^n|x\in {\mathbb R}\}$. Previously, the special cases of this statement for certain $X$ were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of $\mathfrak S_n$-equivariant maps from the boundary $\partial\Delta^{n-1}$ of $(n-1)$-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser's conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem.}, author = {Avvakumov, Sergey and Kudrya, Sergey}, booktitle = {arXiv}, publisher = {arXiv}, title = {{Vanishing of all equivariant obstructions and the mapping degree}}, year = {2019}, } @unpublished{8184, abstract = {Denote by ∆N the N-dimensional simplex. A map f : ∆N → Rd is an almost r-embedding if fσ1∩. . .∩fσr = ∅ whenever σ1, . . . , σr are pairwise disjoint faces. A counterexample to the topological Tverberg conjecture asserts that if r is not a prime power and d ≥ 2r + 1, then there is an almost r-embedding ∆(d+1)(r−1) → Rd. This was improved by Blagojevi´c–Frick–Ziegler using a simple construction of higher-dimensional counterexamples by taking k-fold join power of lower-dimensional ones. We improve this further (for d large compared to r): If r is not a prime power and N := (d+ 1)r−r l d + 2 r + 1 m−2, then there is an almost r-embedding ∆N → Rd. For the r-fold van Kampen–Flores conjecture we also produce counterexamples which are stronger than previously known. Our proof is based on generalizations of the Mabillard–Wagner theorem on construction of almost r-embeddings from equivariant maps, and of the Ozaydin theorem on existence of equivariant maps. }, author = {Avvakumov, Sergey and Karasev, R. and Skopenkov, A.}, booktitle = {arXiv}, publisher = {arXiv}, title = {{Stronger counterexamples to the topological Tverberg conjecture}}, year = {2019}, } @unpublished{8185, abstract = {In this paper we study envy-free division problems. The classical approach to some of such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem) is a certain boundary condition. We follow Erel Segal-Halevi, Fr\'ed\'eric Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the economic meaning of possibility for a player to prefer an empty part in the segment partition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free partition problems when $n$ is odd and not a prime power.}, author = {Avvakumov, Sergey and Karasev, Roman}, booktitle = {arXiv}, title = {{Envy-free division using mapping degree}}, doi = {10.48550/arXiv.1907.11183}, year = {2019}, } @article{6638, abstract = {The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one.}, author = {Silva, André and Arroyo Guevara, Alan M and Richter, Bruce and Lee, Orlando}, issn = {0012-365X}, journal = {Discrete Mathematics}, number = {11}, pages = {3201--3207}, publisher = {Elsevier}, title = {{Graphs with at most one crossing}}, doi = {10.1016/j.disc.2019.06.031}, volume = {342}, year = {2019}, } @inproceedings{6647, abstract = {The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.}, author = {Fulek, Radoslav and Gärtner, Bernd and Kupavskii, Andrey and Valtr, Pavel and Wagner, Uli}, booktitle = {35th International Symposium on Computational Geometry}, isbn = {9783959771047}, issn = {1868-8969}, location = {Portland, OR, United States}, pages = {38:1--38:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The crossing Tverberg theorem}}, doi = {10.4230/LIPICS.SOCG.2019.38}, volume = {129}, year = {2019}, } @phdthesis{6681, abstract = {The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2. However, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2, we construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X). In the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space.}, author = {Zhechev, Stephan Y}, issn = {2663-337X}, pages = {104}, publisher = {Institute of Science and Technology Austria}, title = {{Algorithmic aspects of homotopy theory and embeddability}}, doi = {10.15479/AT:ISTA:6681}, year = {2019}, } @article{6982, abstract = {We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to the same point or overlapping arcs due to data compression or low resolution. This raises the computational problem of deciding whether a given map ϕ : G → M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed into an embedding ψ ϵ : G → M with ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ > 0, where ‖.‖ is the unform norm. A polynomial-time algorithm for recognizing weak embeddings has recently been found by Fulek and Kynčl. It reduces the problem to solving a system of linear equations over Z2. It runs in O(n2ω)≤ O(n4.75) time, where ω ∈ [2,2.373) is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler: We perform a sequence of local operations that gradually “untangles” the image ϕ(G) into an embedding ψ(G) or reports that ϕ is not a weak embedding. It combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations. }, author = {Akitaya, Hugo and Fulek, Radoslav and Tóth, Csaba}, journal = {ACM Transactions on Algorithms}, number = {4}, publisher = {ACM}, title = {{Recognizing weak embeddings of graphs}}, doi = {10.1145/3344549}, volume = {15}, year = {2019}, } @article{7034, abstract = {We find a graph of genus 5 and its drawing on the orientable surface of genus 4 with every pair of independent edges crossing an even number of times. This shows that the strong Hanani–Tutte theorem cannot be extended to the orientable surface of genus 4. As a base step in the construction we use a counterexample to an extension of the unified Hanani–Tutte theorem on the torus.}, author = {Fulek, Radoslav and Kynčl, Jan}, issn = {1439-6912}, journal = {Combinatorica}, number = {6}, pages = {1267--1279}, publisher = {Springer Nature}, title = {{Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4}}, doi = {10.1007/s00493-019-3905-7}, volume = {39}, year = {2019}, } @article{7093, abstract = {In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1)).}, author = {Huszár, Kristóf and Spreer, Jonathan and Wagner, Uli}, issn = {1920-180X}, journal = {Journal of Computational Geometry}, number = {2}, pages = {70–98}, publisher = {Computational Geometry Laborartoy}, title = {{On the treewidth of triangulated 3-manifolds}}, doi = {10.20382/JOGC.V10I2A5}, volume = {10}, year = {2019}, }