---
_id: '7806'
abstract:
- lang: eng
  text: "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?\r\nThe
    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
    .\r\nHere, 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.\r\nOur 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."
article_processing_charge: No
author:
- first_name: Marek
  full_name: Filakovský, Marek
  id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
  last_name: Filakovský
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
- first_name: Stephan Y
  full_name: Zhechev, Stephan Y
  id: 3AA52972-F248-11E8-B48F-1D18A9856A87
  last_name: Zhechev
citation:
  ama: 'Filakovský M, Wagner U, Zhechev SY. Embeddability of simplicial complexes
    is undecidable. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete
    Algorithms</i>. Vol 2020-January. SIAM; 2020:767-785. doi:<a href="https://doi.org/10.1137/1.9781611975994.47">10.1137/1.9781611975994.47</a>'
  apa: 'Filakovský, M., Wagner, U., &#38; Zhechev, S. Y. (2020). Embeddability of
    simplicial complexes is undecidable. In <i>Proceedings of the Annual ACM-SIAM
    Symposium on Discrete Algorithms</i> (Vol. 2020–January, pp. 767–785). Salt Lake
    City, UT, United States: SIAM. <a href="https://doi.org/10.1137/1.9781611975994.47">https://doi.org/10.1137/1.9781611975994.47</a>'
  chicago: Filakovský, Marek, Uli Wagner, and Stephan Y Zhechev. “Embeddability of
    Simplicial Complexes Is Undecidable.” In <i>Proceedings of the Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>, 2020–January:767–85. SIAM, 2020. <a href="https://doi.org/10.1137/1.9781611975994.47">https://doi.org/10.1137/1.9781611975994.47</a>.
  ieee: M. Filakovský, U. Wagner, and S. Y. Zhechev, “Embeddability of simplicial
    complexes is undecidable,” in <i>Proceedings of the Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January,
    pp. 767–785.
  ista: 'Filakovský M, Wagner U, Zhechev SY. 2020. Embeddability of simplicial complexes
    is undecidable. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
    SODA: Symposium on Discrete Algorithms vol. 2020–January, 767–785.'
  mla: Filakovský, Marek, et al. “Embeddability of Simplicial Complexes Is Undecidable.”
    <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol.
    2020–January, SIAM, 2020, pp. 767–85, doi:<a href="https://doi.org/10.1137/1.9781611975994.47">10.1137/1.9781611975994.47</a>.
  short: M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM
    Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785.
conference:
  end_date: 2020-01-08
  location: Salt Lake City, UT, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2020-01-05
date_created: 2020-05-10T22:00:48Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2021-01-12T08:15:38Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/1.9781611975994.47
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1137/1.9781611975994.47
month: '01'
oa: 1
oa_version: Published Version
page: 767-785
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '9781611975994'
publication_status: published
publisher: SIAM
quality_controlled: '1'
scopus_import: 1
status: public
title: Embeddability of simplicial complexes is undecidable
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2020-January
year: '2020'
...
---
_id: '7807'
abstract:
- lang: eng
  text: "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.\r\nFor
    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).\r\nA 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."
article_processing_charge: No
arxiv: 1
author:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: 'Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane
    (Part I: Edge flips). In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete
    Algorithms</i>. Vol 2020-January. SIAM; 2020:2823-2841. doi:<a href="https://doi.org/10.1137/1.9781611975994.172">10.1137/1.9781611975994.172</a>'
  apa: 'Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs
    in the plane (Part I: Edge flips). In <i>Proceedings of the Annual ACM-SIAM Symposium
    on Discrete Algorithms</i> (Vol. 2020–January, pp. 2823–2841). Salt Lake City,
    UT, United States: SIAM. <a href="https://doi.org/10.1137/1.9781611975994.172">https://doi.org/10.1137/1.9781611975994.172</a>'
  chicago: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
    in the Plane (Part I: Edge Flips).” In <i>Proceedings of the Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>, 2020–January:2823–41. SIAM, 2020. <a href="https://doi.org/10.1137/1.9781611975994.172">https://doi.org/10.1137/1.9781611975994.172</a>.'
  ieee: 'U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
    plane (Part I: Edge flips),” in <i>Proceedings of the Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January,
    pp. 2823–2841.'
  ista: 'Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the
    plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete
    Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.'
  mla: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in
    the Plane (Part I: Edge Flips).” <i>Proceedings of the Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:<a
    href="https://doi.org/10.1137/1.9781611975994.172">10.1137/1.9781611975994.172</a>.'
  short: U. Wagner, E. Welzl, in:, Proceedings of the Annual ACM-SIAM Symposium on
    Discrete Algorithms, SIAM, 2020, pp. 2823–2841.
conference:
  end_date: 2020-01-08
  location: Salt Lake City, UT, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2020-01-05
date_created: 2020-05-10T22:00:48Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2024-10-09T21:03:33Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/1.9781611975994.172
external_id:
  arxiv:
  - '2003.13557'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1137/1.9781611975994.172
month: '01'
oa: 1
oa_version: Submitted Version
page: 2823-2841
publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '9781611975994'
publication_status: published
publisher: SIAM
quality_controlled: '1'
related_material:
  record:
  - id: '12129'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: 'Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2020-January
year: '2020'
...