@unpublished{6313,
abstract = {We prove three principal results. First we exhibit a drawing of $K_{10}$ in the plane for which there do not exist extensions of the edges to simple closed curves with any two curves intersecting at most twice. Second, we exhibit a drawing of $K_9$ that has an extension of its edges to simple closed curves such that any two curves intersect in at most two points, but no extension to simple closed curves has every two curves intersecting in exactly two points. Third, we show that every h-convex drawing (introduced by Arroyo et al, submitted) has extensions of its edges to simple closed curves such that any two curves intersect in exactly two points. Using this result, we show that} a set of three axioms of simple closed curve extensions characterizes h-convexity.},
author = {Arroyo Guevara, Alan M and Richter, Bruce and Sunohara, Matthew},
pages = {35},
title = {{Extending drawings of complete graphs into arrangements of pseudocircles}},
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},
}
@article{7108,
abstract = {We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable.},
author = {Goaoc, Xavier and Patak, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
issn = {0004-5411},
journal = {Journal of the ACM},
number = {3},
publisher = {ACM},
title = {{Shellability is NP-complete}},
doi = {10.1145/3314024},
volume = {66},
year = {2019},
}
@article{5986,
abstract = {Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.},
author = {Lubiw, Anna and Masárová, Zuzana and Wagner, Uli},
issn = {0179-5376},
journal = {Discrete & Computational Geometry},
number = {4},
pages = {880--898},
publisher = {Springer Nature},
title = {{A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations}},
doi = {10.1007/s00454-018-0035-8},
volume = {61},
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 = {IST Austria},
title = {{Algorithmic aspects of homotopy theory and embeddability}},
doi = {10.15479/AT:ISTA:6681},
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},
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},
year = {2019},
}
@inproceedings{6556,
abstract = {Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.},
author = {Huszár, Kristóf and Spreer, Jonathan},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
isbn = {978-3-95977-104-7},
issn = {1868-8969},
keyword = {computational 3-manifold topology, fixed-parameter tractability, layered triangulations, structural graph theory, treewidth, cutwidth, Heegaard genus},
location = {Portland, Oregon, United States},
pages = {44:1--44:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
title = {{3-manifold triangulations with small treewidth}},
doi = {10.4230/LIPIcs.SoCG.2019.44},
volume = {129},
year = {2019},
}
@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},
publisher = {Springer Nature},
title = {{Are two given maps homotopic? An algorithmic viewpoint}},
doi = {10.1007/s10208-019-09419-x},
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},
journal = {Discrete Mathematics},
publisher = {Elsevier},
title = {{Graphs with at most one crossing}},
doi = {10.1016/j.disc.2019.06.031},
year = {2019},
}
@article{5857,
abstract = {A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1), and that this bound is best possible for infinitely many values of n.},
author = {Fulek, Radoslav and Pach, János},
issn = {0166218X},
journal = {Discrete Applied Mathematics},
number = {4},
pages = {266--231},
publisher = {Elsevier},
title = {{Thrackles: An improved upper bound}},
doi = {10.1016/j.dam.2018.12.025},
volume = {259},
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{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},
}
@inproceedings{186,
abstract = {A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t × t grid or one of the following so-called t-Kuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its ℤ2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces.},
author = {Fulek, Radoslav and Kynčl, Jan},
location = {Budapest, Hungary},
pages = {401 -- 4014},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{The ℤ2-Genus of Kuratowski minors}},
doi = {10.4230/LIPIcs.SoCG.2018.40},
volume = {99},
year = {2018},
}
@article{5790,
abstract = {The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.},
author = {Chaplick, Steven and Fulek, Radoslav and Klavík, Pavel},
issn = {03649024},
journal = {Journal of Graph Theory},
publisher = {Wiley},
title = {{Extending partial representations of circle graphs}},
doi = {10.1002/jgt.22436},
year = {2018},
}
@article{6774,
abstract = {A central problem of algebraic topology is to understand the homotopy groups 𝜋𝑑(𝑋) of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group 𝜋1(𝑋) 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(𝑋) trivial), compute the higher homotopy group 𝜋𝑑(𝑋) for any given 𝑑≥2 . However, these algorithms come with a caveat: They compute the isomorphism type of 𝜋𝑑(𝑋) , 𝑑≥2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of 𝜋𝑑(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere 𝑆𝑑 to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes 𝜋𝑑(𝑋) and represents its elements as simplicial maps from a suitable triangulation of the d-sphere 𝑆𝑑 to X. For fixed d, the algorithm runs in time exponential in size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed 𝑑≥2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of 𝜋𝑑(𝑋) , the size of the triangulation of 𝑆𝑑 on which the map is defined, is exponential in size(𝑋) .},
author = {Filakovský, Marek and Franek, Peter and Wagner, Uli and Zhechev, Stephan Y},
issn = {2367-1734},
journal = {Journal of Applied and Computational Topology},
number = {3-4},
pages = {177--231},
publisher = {Springer},
title = {{Computing simplicial representatives of homotopy group elements}},
doi = {10.1007/s41468-018-0021-5},
volume = {2},
year = {2018},
}
@inproceedings{5791,
abstract = {Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε>0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An ε-perturbation, for every ε>0, is given by a piecewise linear map (Formula Presented), where with ||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths.},
author = {Fulek, Radoslav and Tóth, Csaba D.},
isbn = {9783030044138},
location = {Barcelona, Spain},
pages = {229--241},
publisher = {Springer},
title = {{Crossing minimization in perturbed drawings}},
doi = {10.1007/978-3-030-04414-5_16},
volume = {11282 },
year = {2018},
}
@inproceedings{309,
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 2manifold 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 a common node or arc, 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 k' "k < " for every " > 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2!) O(n4:75) time, where 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 than [14]: 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 generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and 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},
location = {New Orleans, LA, USA},
pages = {274 -- 292},
publisher = {ACM},
title = {{Recognizing weak embeddings of graphs}},
doi = {10.1137/1.9781611975031.20},
year = {2018},
}
@article{425,
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 R3? 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, that is, an essential curve in the boundary of X bounding a disk in S3 \ X 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},
journal = {Journal of the ACM},
number = {1},
publisher = {ACM},
title = {{Embeddability in the 3-Sphere is decidable}},
doi = {10.1145/3078632},
volume = {65},
year = {2018},
}
@article{742,
abstract = {We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M.},
author = {Dotterrer, Dominic and Kaufman, Tali and Wagner, Uli},
journal = {Geometriae Dedicata},
number = {1},
pages = {307–317},
publisher = {Springer},
title = {{On expansion and topological overlap}},
doi = {10.1007/s10711-017-0291-4},
volume = {195},
year = {2018},
}
@inproceedings{184,
abstract = {We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.},
author = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
location = {Budapest, Hungary},
pages = {41:1 -- 41:16},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Shellability is NP-complete}},
doi = {10.4230/LIPIcs.SoCG.2018.41},
volume = {99},
year = {2018},
}