@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{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},
}
@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{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},
}
@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},
}
@inproceedings{7230,
abstract = {Simple drawings of graphs are those in which each pair of edges share at most one point, either a common endpoint or a proper crossing. In this paper we study the problem of extending a simple drawing D(G) of a graph G by inserting a set of edges from the complement of G into D(G) such that the result is a simple drawing. In the context of rectilinear drawings, the problem is trivial. For pseudolinear drawings, the existence of such an extension follows from Levi’s enlargement lemma. In contrast, we prove that deciding if a given set of edges can be inserted into a simple drawing is NP-complete. Moreover, we show that the maximization version of the problem is APX-hard. We also present a polynomial-time algorithm for deciding whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for the graph G.},
author = {Arroyo Guevara, Alan M and Derka, Martin and Parada, Irene},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
isbn = {9783030358013},
issn = {16113349},
location = {Prague, Czech Republic},
pages = {230--243},
publisher = {Springer Nature},
title = {{Extending simple drawings}},
doi = {10.1007/978-3-030-35802-0_18},
volume = {11904},
year = {2019},
}
@inproceedings{7401,
abstract = {The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. 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 Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. },
author = {Fulek, Radoslav and Kyncl, Jan},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
isbn = {978-3-95977-104-7},
issn = {1868-8969},
location = {Portland, OR, United States},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Z_2-Genus of graphs and minimum rank of partial symmetric matrices}},
doi = {10.4230/LIPICS.SOCG.2019.39},
volume = {129},
year = {2019},
}
@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:1903.06981},
pages = {41},
publisher = {ArXiv},
title = {{Token swapping on trees}},
year = {2019},
}
@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},
}
@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},
keywords = {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 für Informatik},
title = {{3-manifold triangulations with small treewidth}},
doi = {10.4230/LIPIcs.SoCG.2019.44},
volume = {129},
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},
}