@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{7806,
abstract = {We consider the following decision problem EMBEDkād in computational topology (where k ā¤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ād?
The special case EMBED1ā2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2ā3 and EMBED3ā3 are known to be decidable (as well as NP-hard), and recent results of Äadek et al. in computational homotopy theory, in combination with the classical HaefligerāWeber theorem in geometric topology, imply that EMBEDkād can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range .
Here, by contrast, we prove that EMBEDkād is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDkād in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.
Our result complements (and in a wide range of dimensions strengthens) earlier results of MatouÅ”ek, Tancer, and the second author, who showed that EMBEDkād is undecidable for 4 ā¤ k Ļµ {d ā 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ā„ 4.},
author = {FilakovskĆ½, Marek and Wagner, Uli and Zhechev, Stephan Y},
booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms},
isbn = {9781611975994},
location = {Salt Lake City, UT, United States},
pages = {767--785},
publisher = {SIAM},
title = {{Embeddability of simplicial complexes is undecidable}},
doi = {10.1137/1.9781611975994.47},
volume = {2020-January},
year = {2020},
}
@inproceedings{7807,
abstract = {In a straight-line embedded triangulation of a point set P in the plane, removing an inner edge andāprovided the resulting quadrilateral is convexāadding the other diagonal is called an edge flip. The (edge) flip graph has all triangulations as vertices, and a pair of triangulations is adjacent if they can be obtained from each other by an edge flip. The goal of this paper is to contribute to a better understanding of the flip graph, with an emphasis on its connectivity.
For sets in general position, it is known that every triangulation allows at least edge flips (a tight bound) which gives the minimum degree of any flip graph for n points. We show that for every point set P in general position, the flip graph is at least -vertex connected. Somewhat more strongly, we show that the vertex connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P, provided P is large enough. Finally, we exhibit some of the geometry of the flip graph by showing that the flip graph can be covered by 1-skeletons of polytopes of dimension (products of associahedra).
A corresponding result ((n ā 3)-vertex connectedness) can be shown for the bistellar flip graph of partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. This will be treated separately in a second part.},
author = {Wagner, Uli and Welzl, Emo},
booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms},
isbn = {9781611975994},
location = {Salt Lake City, UT, United States},
pages = {2823--2841},
publisher = {SIAM},
title = {{Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)}},
doi = {10.1137/1.9781611975994.172},
volume = {2020-January},
year = {2020},
}
@phdthesis{7944,
abstract = {This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures ā all the triangulations of a given point set or all token placements on a given graph ā can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation ā by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.
For triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.
In the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars.},
author = {MasĆ”rovĆ”, Zuzana},
isbn = {978-3-99078-005-3},
issn = {2663-337X},
keywords = {reconfiguration, reconfiguration graph, triangulations, flip, constrained triangulations, shellability, piecewise-linear balls, token swapping, trees, coloured weighted token swapping},
pages = {160},
publisher = {IST Austria},
title = {{Reconfiguration problems}},
doi = {10.15479/AT:ISTA:7944},
year = {2020},
}
@article{7960,
abstract = {Let A={A1,ā¦,An} be a family of sets in the plane. For 0ā¤i2b be integers. We prove that if each k-wise or (k+1)-wise intersection of sets from A has at most b path-connected components, which all are open, then fk+1=0 implies fkā¤cfkā1 for some positive constant c depending only on b and k. These results also extend to two-dimensional compact surfaces.},
author = {Kalai, Gil and Patakova, Zuzana},
issn = {14320444},
journal = {Discrete and Computational Geometry},
publisher = {Springer Nature},
title = {{Intersection patterns of planar sets}},
doi = {10.1007/s00454-020-00205-z},
year = {2020},
}
@inproceedings{7989,
abstract = {We prove general topological Radon-type theorems for sets in ā^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak Īµ-nets as well as a (p,q)-theorem. More precisely: Let X be either ā^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ā¤ā coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ā^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface.},
author = {Patakova, Zuzana},
booktitle = {36th International Symposium on Computational Geometry},
isbn = {9783959771436},
issn = {18688969},
location = {ZĆ¼rich, Switzerland},
pages = {61:1--61:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fĆ¼r Informatik},
title = {{Bounding radon number via Betti numbers}},
doi = {10.4230/LIPIcs.SoCG.2020.61},
volume = {164},
year = {2020},
}
@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},
pages = {12:1 -- 12:15},
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{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},
pages = {119},
publisher = {IST Austria},
title = {{Topological methods in geometry and discrete mathematics}},
doi = {10.15479/AT:ISTA:8156},
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 = {IST Austria},
title = {{Combinatorial width parameters for 3-dimensional manifolds}},
doi = {10.15479/AT:ISTA:8032},
year = {2020},
}
@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},
number = {4},
pages = {365--394},
publisher = {Wiley},
title = {{Extending partial representations of circle graphs}},
doi = {10.1002/jgt.22436},
volume = {91},
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{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},
}
@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 = {IST 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},
}