@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},
}
@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},
}
@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},
}
@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},
}
@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},
pages = {1--19},
publisher = {Springer Nature America},
title = {{A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations}},
doi = {10.1007/s00454-018-0035-8},
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},
}
@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},
}
@inproceedings{285,
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 and of Scharlemann and Thompson, 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 48(k+1) (resp. 4(3k+1)).},
author = {Huszár, Kristóf and Spreer, Jonathan and Wagner, Uli},
issn = {18688969},
location = {Budapest, Hungary},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{On the Treewidth of Triangulated 3-Manifolds}},
doi = {10.4230/LIPIcs.SoCG.2018.46},
volume = {99},
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{185,
abstract = {We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.},
author = {Fulek, Radoslav and Kynčl, Jan},
isbn = {978-3-95977-066-8},
location = {Budapest, Hungary},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Hanani-Tutte for approximating maps of graphs}},
doi = {10.4230/LIPIcs.SoCG.2018.39},
volume = {99},
year = {2018},
}
@article{5960,
abstract = {In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a bounded-error context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion.},
author = {Rohou, Simon and Franek, Peter and Aubry, Clément and Jaulin, Luc},
issn = {0278-3649},
journal = {The International Journal of Robotics Research},
number = {12},
pages = {1500--1516},
publisher = {SAGE Publications},
title = {{Proving the existence of loops in robot trajectories}},
doi = {10.1177/0278364918808367},
volume = {37},
year = {2018},
}
@inproceedings{433,
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 3/2(n-1), and that this bound is best possible for infinitely many values of n.},
author = {Fulek, Radoslav and Pach, János},
pages = {160 -- 166},
publisher = {Springer},
title = {{Thrackles: An Improved Upper Bound}},
doi = {10.1007/978-3-319-73915-1_14},
volume = {10692},
year = {2018},
}