---
_id: '7960'
abstract:
- lang: eng
  text: Let A={A1,…,An} be a family of sets in the plane. For 0≤i<n, denote by fi
    the number of subsets σ of {1,…,n} of cardinality i+1 that satisfy ⋂i∈σAi≠∅. Let
    k≥2 be an integer. We prove that if each k-wise and (k+1)-wise intersection of
    sets from A is empty, or a single point, or both open and path-connected, then
    fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on k. Similarly,
    let b≥2, k>2b 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.
acknowledgement: "We are very grateful to Pavel Paták for many helpful discussions
  and remarks. We also thank the referees for helpful comments, which greatly improved
  the presentation.\r\nThe project was supported by ERC Advanced Grant 320924. GK
  was also partially supported by NSF grant DMS1300120. The research stay of ZP at
  IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement
  of internationalization in the field of research and development at Charles University,
  through the support of quality projects MSCA-IF."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Gil
  full_name: Kalai, Gil
  last_name: Kalai
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
citation:
  ama: Kalai G, Patakova Z. Intersection patterns of planar sets. <i>Discrete and
    Computational Geometry</i>. 2020;64:304-323. doi:<a href="https://doi.org/10.1007/s00454-020-00205-z">10.1007/s00454-020-00205-z</a>
  apa: Kalai, G., &#38; Patakova, Z. (2020). Intersection patterns of planar sets.
    <i>Discrete and Computational Geometry</i>. Springer Nature. <a href="https://doi.org/10.1007/s00454-020-00205-z">https://doi.org/10.1007/s00454-020-00205-z</a>
  chicago: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.”
    <i>Discrete and Computational Geometry</i>. Springer Nature, 2020. <a href="https://doi.org/10.1007/s00454-020-00205-z">https://doi.org/10.1007/s00454-020-00205-z</a>.
  ieee: G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” <i>Discrete
    and Computational Geometry</i>, vol. 64. Springer Nature, pp. 304–323, 2020.
  ista: Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete
    and Computational Geometry. 64, 304–323.
  mla: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” <i>Discrete
    and Computational Geometry</i>, vol. 64, Springer Nature, 2020, pp. 304–23, doi:<a
    href="https://doi.org/10.1007/s00454-020-00205-z">10.1007/s00454-020-00205-z</a>.
  short: G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323.
date_created: 2020-06-14T22:00:50Z
date_published: 2020-09-01T00:00:00Z
date_updated: 2023-08-21T08:26:34Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-020-00205-z
external_id:
  arxiv:
  - '1907.00885'
  isi:
  - '000537329400001'
intvolume: '        64'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1907.00885
month: '09'
oa: 1
oa_version: Preprint
page: 304-323
publication: Discrete and Computational Geometry
publication_identifier:
  eissn:
  - '14320444'
  issn:
  - '01795376'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Intersection patterns of planar sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...
---
_id: '7989'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LIPIcs
article_number: 61:1-61:13
article_processing_charge: No
arxiv: 1
author:
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
citation:
  ama: 'Patakova Z. Bounding radon number via Betti numbers. In: <i>36th International
    Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">10.4230/LIPIcs.SoCG.2020.61</a>'
  apa: 'Patakova, Z. (2020). Bounding radon number via Betti numbers. In <i>36th International
    Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">https://doi.org/10.4230/LIPIcs.SoCG.2020.61</a>'
  chicago: Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In <i>36th
    International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">https://doi.org/10.4230/LIPIcs.SoCG.2020.61</a>.
  ieee: Z. Patakova, “Bounding radon number via Betti numbers,” in <i>36th International
    Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.
  ista: 'Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International
    Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry,
    LIPIcs, vol. 164, 61:1-61:13.'
  mla: Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” <i>36th International
    Symposium on Computational Geometry</i>, vol. 164, 61:1-61:13, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2020, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">10.4230/LIPIcs.SoCG.2020.61</a>.
  short: Z. Patakova, in:, 36th International Symposium on Computational Geometry,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-06-26
  location: Zürich, Switzerland
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2020-06-22
corr_author: '1'
date_created: 2020-06-22T09:14:18Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2025-07-10T11:54:54Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.61
external_id:
  arxiv:
  - '1908.01677'
file:
- access_level: open_access
  checksum: d0996ca5f6eb32ce955ce782b4f2afbe
  content_type: application/pdf
  creator: dernst
  date_created: 2020-06-23T06:56:23Z
  date_updated: 2020-07-14T12:48:06Z
  file_id: '8005'
  file_name: 2020_LIPIcsSoCG_Patakova_61.pdf
  file_size: 645421
  relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: '       164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 36th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771436'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bounding radon number via Betti numbers
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_id: '7990'
abstract:
- lang: eng
  text: '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).'
alternative_title:
- LIPIcs
article_number: 67:1 - 67:16
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 II: Bistellar flips). In: <i>36th International Symposium on Computational
    Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020.
    doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.67">10.4230/LIPIcs.SoCG.2020.67</a>'
  apa: 'Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs
    in the plane (Part II: Bistellar flips). In <i>36th International Symposium on
    Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl -
    Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.67">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>'
  chicago: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
    in the Plane (Part II: Bistellar Flips).” In <i>36th International Symposium on
    Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2020. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.67">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>.'
  ieee: 'U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
    plane (Part II: Bistellar flips),” in <i>36th International Symposium on Computational
    Geometry</i>, Zürich, Switzerland, 2020, vol. 164.'
  ista: 'Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the
    plane (Part II: Bistellar flips). 36th International Symposium on Computational
    Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 67:1-67:16.'
  mla: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in
    the Plane (Part II: Bistellar Flips).” <i>36th International Symposium on Computational
    Geometry</i>, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2020, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.67">10.4230/LIPIcs.SoCG.2020.67</a>.'
  short: U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-06-26
  location: Zürich, Switzerland
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2020-06-22
corr_author: '1'
date_created: 2020-06-22T09:14:19Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2025-07-10T11:54:56Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.67
external_id:
  arxiv:
  - '2003.13557'
file:
- access_level: open_access
  checksum: 3f6925be5f3dcdb3b14cab92f410edf7
  content_type: application/pdf
  creator: dernst
  date_created: 2020-06-23T06:37:27Z
  date_updated: 2020-07-14T12:48:06Z
  file_id: '8003'
  file_name: 2020_LIPIcsSoCG_Wagner.pdf
  file_size: 793187
  relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: '       164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 36th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771436'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
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 II: Bistellar
  flips)'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_id: '7991'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LIPIcs
article_number: 12:1 - 12:15
article_processing_charge: No
arxiv: 1
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: Gabriel
  full_name: Nivasch, Gabriel
  last_name: Nivasch
citation:
  ama: 'Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening
    flow. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.12">10.4230/LIPIcs.SoCG.2020.12</a>'
  apa: 'Avvakumov, S., &#38; Nivasch, G. (2020). Homotopic curve shortening and the
    affine curve-shortening flow. In <i>36th International Symposium on Computational
    Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.12">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>'
  chicago: Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and
    the Affine Curve-Shortening Flow.” In <i>36th International Symposium on Computational
    Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
    <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.12">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>.
  ieee: S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening
    flow,” in <i>36th International Symposium on Computational Geometry</i>, Zürich,
    Switzerland, 2020, vol. 164.
  ista: 'Avvakumov S, Nivasch G. 2020. Homotopic curve shortening and the affine curve-shortening
    flow. 36th International Symposium on Computational Geometry. SoCG: Symposium
    on Computational Geometry, LIPIcs, vol. 164, 12:1-12:15.'
  mla: Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the
    Affine Curve-Shortening Flow.” <i>36th International Symposium on Computational
    Geometry</i>, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2020, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.12">10.4230/LIPIcs.SoCG.2020.12</a>.
  short: S. Avvakumov, G. Nivasch, in:, 36th International Symposium on Computational
    Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-06-26
  location: Zürich, Switzerland
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2020-06-22
date_created: 2020-06-22T09:14:19Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2025-07-10T11:54:56Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.12
external_id:
  arxiv:
  - '1909.00263'
file:
- access_level: open_access
  checksum: 6872df6549142f709fb6354a1b2f2c06
  content_type: application/pdf
  creator: dernst
  date_created: 2020-06-23T11:13:49Z
  date_updated: 2020-07-14T12:48:06Z
  file_id: '8007'
  file_name: 2020_LIPIcsSoCG_Avvakumov.pdf
  file_size: 575896
  relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: '       164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
publication: 36th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771436'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Homotopic curve shortening and the affine curve-shortening flow
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
  name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
  short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_id: '7992'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LIPIcs
article_number: 62:1 - 62:16
article_processing_charge: No
arxiv: 1
author:
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
- first_name: Martin
  full_name: Tancer, Martin
  id: 38AC689C-F248-11E8-B48F-1D18A9856A87
  last_name: Tancer
  orcid: 0000-0002-1191-6714
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In:
    <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.62">10.4230/LIPIcs.SoCG.2020.62</a>'
  apa: 'Patakova, Z., Tancer, M., &#38; Wagner, U. (2020). Barycentric cuts through
    a convex body. In <i>36th International Symposium on Computational Geometry</i>
    (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.62">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>'
  chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
    a Convex Body.” In <i>36th International Symposium on Computational Geometry</i>,
    Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.62">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>.
  ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
    body,” in <i>36th International Symposium on Computational Geometry</i>, Zürich,
    Switzerland, 2020, vol. 164.
  ista: 'Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body.
    36th International Symposium on Computational Geometry. SoCG: Symposium on Computational
    Geometry, LIPIcs, vol. 164, 62:1-62:16.'
  mla: Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>36th
    International Symposium on Computational Geometry</i>, vol. 164, 62:1-62:16, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.62">10.4230/LIPIcs.SoCG.2020.62</a>.
  short: Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational
    Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-06-26
  location: Zürich, Switzerland
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2020-06-22
corr_author: '1'
date_created: 2020-06-22T09:14:20Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2025-07-10T11:54:57Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.62
external_id:
  arxiv:
  - '2003.13536'
file:
- access_level: open_access
  checksum: ce1c9194139a664fb59d1efdfc88eaae
  content_type: application/pdf
  creator: dernst
  date_created: 2020-06-23T06:45:52Z
  date_updated: 2020-07-14T12:48:06Z
  file_id: '8004'
  file_name: 2020_LIPIcsSoCG_Patakova.pdf
  file_size: 750318
  relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: '       164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 36th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771436'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Barycentric cuts through a convex body
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_id: '7994'
abstract:
- lang: eng
  text: 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.
alternative_title:
- LIPIcs
article_number: 9:1 - 9:14
article_processing_charge: No
arxiv: 1
author:
- first_name: Alan M
  full_name: Arroyo Guevara, Alan M
  id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
  last_name: Arroyo Guevara
  orcid: 0000-0003-2401-8670
- first_name: Julien
  full_name: Bensmail, Julien
  last_name: Bensmail
- first_name: R.
  full_name: Bruce Richter, R.
  last_name: Bruce Richter
citation:
  ama: 'Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs
    to arrangements of pseudolines. In: <i>36th International Symposium on Computational
    Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020.
    doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.9">10.4230/LIPIcs.SoCG.2020.9</a>'
  apa: 'Arroyo Guevara, A. M., Bensmail, J., &#38; Bruce Richter, R. (2020). Extending
    drawings of graphs to arrangements of pseudolines. In <i>36th International Symposium
    on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.9">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>'
  chicago: Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending
    Drawings of Graphs to Arrangements of Pseudolines.” In <i>36th International Symposium
    on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.9">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>.
  ieee: A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings
    of graphs to arrangements of pseudolines,” in <i>36th International Symposium
    on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.
  ista: 'Arroyo Guevara AM, Bensmail J, Bruce Richter R. 2020. Extending drawings
    of graphs to arrangements of pseudolines. 36th International Symposium on Computational
    Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 9:1-9:14.'
  mla: Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements
    of Pseudolines.” <i>36th International Symposium on Computational Geometry</i>,
    vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a
    href="https://doi.org/10.4230/LIPIcs.SoCG.2020.9">10.4230/LIPIcs.SoCG.2020.9</a>.
  short: A.M. Arroyo Guevara, J. Bensmail, R. Bruce Richter, in:, 36th International
    Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2020.
conference:
  end_date: 2020-06-26
  location: Zürich, Switzerland
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2020-06-22
corr_author: '1'
date_created: 2020-06-22T09:14:21Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2025-07-10T11:54:58Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.9
ec_funded: 1
external_id:
  arxiv:
  - '1804.09317'
file:
- access_level: open_access
  checksum: 93571b76cf97d5b7c8aabaeaa694dd7e
  content_type: application/pdf
  creator: dernst
  date_created: 2020-06-23T11:06:23Z
  date_updated: 2020-07-14T12:48:06Z
  file_id: '8006'
  file_name: 2020_LIPIcsSoCG_Arroyo.pdf
  file_size: 592661
  relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: '       164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 36th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771436'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending drawings of graphs to arrangements of pseudolines
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
OA_place: publisher
_id: '8032'
abstract:
- lang: eng
  text: "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.”\r\nIn 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."
acknowledged_ssus:
- _id: E-Lib
- _id: CampIT
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Kristóf
  full_name: Huszár, Kristóf
  id: 33C26278-F248-11E8-B48F-1D18A9856A87
  last_name: Huszár
  orcid: 0000-0002-5445-5057
citation:
  ama: Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020.
    doi:<a href="https://doi.org/10.15479/AT:ISTA:8032">10.15479/AT:ISTA:8032</a>
  apa: Huszár, K. (2020). <i>Combinatorial width parameters for 3-dimensional manifolds</i>.
    Institute of Science and Technology Austria. <a href="https://doi.org/10.15479/AT:ISTA:8032">https://doi.org/10.15479/AT:ISTA:8032</a>
  chicago: Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.”
    Institute of Science and Technology Austria, 2020. <a href="https://doi.org/10.15479/AT:ISTA:8032">https://doi.org/10.15479/AT:ISTA:8032</a>.
  ieee: K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute
    of Science and Technology Austria, 2020.
  ista: Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds.
    Institute of Science and Technology Austria.
  mla: Huszár, Kristóf. <i>Combinatorial Width Parameters for 3-Dimensional Manifolds</i>.
    Institute of Science and Technology Austria, 2020, doi:<a href="https://doi.org/10.15479/AT:ISTA:8032">10.15479/AT:ISTA:8032</a>.
  short: K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute
    of Science and Technology Austria, 2020.
corr_author: '1'
date_created: 2020-06-26T10:00:36Z
date_published: 2020-06-26T00:00:00Z
date_updated: 2026-04-08T07:21:28Z
day: '26'
ddc:
- '514'
degree_awarded: PhD
department:
- _id: UlWa
doi: 10.15479/AT:ISTA:8032
file:
- access_level: open_access
  checksum: bd8be6e4f1addc863dfcc0fad29ee9c3
  content_type: application/pdf
  creator: khuszar
  date_created: 2020-06-26T10:03:58Z
  date_updated: 2020-07-14T12:48:08Z
  file_id: '8034'
  file_name: Kristof_Huszar-Thesis.pdf
  file_size: 2637562
  relation: main_file
- access_level: closed
  checksum: d5f8456202b32f4a77552ef47a2837d1
  content_type: application/x-zip-compressed
  creator: khuszar
  date_created: 2020-06-26T10:10:06Z
  date_updated: 2020-07-14T12:48:08Z
  file_id: '8035'
  file_name: Kristof_Huszar-Thesis-source.zip
  file_size: 7163491
  relation: source_file
file_date_updated: 2020-07-14T12:48:08Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: xviii+120
publication_identifier:
  isbn:
  - 978-3-99078-006-0
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
  record:
  - id: '6556'
    relation: dissertation_contains
    status: public
  - id: '7093'
    relation: dissertation_contains
    status: public
status: public
supervisor:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
- first_name: Jonathan
  full_name: Spreer, Jonathan
  last_name: Spreer
title: Combinatorial width parameters for 3-dimensional manifolds
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2020'
...
---
OA_place: publisher
_id: '8156'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
citation:
  ama: Avvakumov S. Topological methods in geometry and discrete mathematics. 2020.
    doi:<a href="https://doi.org/10.15479/AT:ISTA:8156">10.15479/AT:ISTA:8156</a>
  apa: Avvakumov, S. (2020). <i>Topological methods in geometry and discrete mathematics</i>.
    Institute of Science and Technology Austria. <a href="https://doi.org/10.15479/AT:ISTA:8156">https://doi.org/10.15479/AT:ISTA:8156</a>
  chicago: Avvakumov, Sergey. “Topological Methods in Geometry and Discrete Mathematics.”
    Institute of Science and Technology Austria, 2020. <a href="https://doi.org/10.15479/AT:ISTA:8156">https://doi.org/10.15479/AT:ISTA:8156</a>.
  ieee: S. Avvakumov, “Topological methods in geometry and discrete mathematics,”
    Institute of Science and Technology Austria, 2020.
  ista: Avvakumov S. 2020. Topological methods in geometry and discrete mathematics.
    Institute of Science and Technology Austria.
  mla: Avvakumov, Sergey. <i>Topological Methods in Geometry and Discrete Mathematics</i>.
    Institute of Science and Technology Austria, 2020, doi:<a href="https://doi.org/10.15479/AT:ISTA:8156">10.15479/AT:ISTA:8156</a>.
  short: S. Avvakumov, Topological Methods in Geometry and Discrete Mathematics, Institute
    of Science and Technology Austria, 2020.
corr_author: '1'
date_created: 2020-07-23T09:51:29Z
date_published: 2020-07-24T00:00:00Z
date_updated: 2026-04-08T07:25:54Z
day: '24'
ddc:
- '514'
degree_awarded: PhD
department:
- _id: UlWa
doi: 10.15479/AT:ISTA:8156
file:
- access_level: closed
  content_type: application/zip
  creator: savvakum
  date_created: 2020-07-27T12:44:51Z
  date_updated: 2020-07-27T12:44:51Z
  file_id: '8178'
  file_name: source.zip
  file_size: 1061740
  relation: source_file
- access_level: open_access
  content_type: application/pdf
  creator: savvakum
  date_created: 2020-07-27T12:46:53Z
  date_updated: 2020-07-27T12:46:53Z
  file_id: '8179'
  file_name: thesis_pdfa.pdf
  file_size: 1336501
  relation: main_file
  success: 1
file_date_updated: 2020-07-27T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '119'
publication_identifier:
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
  record:
  - id: '8182'
    relation: part_of_dissertation
    status: public
  - id: '8184'
    relation: part_of_dissertation
    status: public
  - id: '8185'
    relation: part_of_dissertation
    status: public
  - id: '6355'
    relation: part_of_dissertation
    status: public
  - id: '75'
    relation: part_of_dissertation
    status: public
  - id: '8183'
    relation: part_of_dissertation
    status: public
status: public
supervisor:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
title: Topological methods in geometry and discrete mathematics
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2020'
...
---
_id: '8732'
abstract:
- lang: eng
  text: 'A simple drawing D(G) of a graph G is one where each pair of edges share
    at most one point: either a common endpoint or a proper crossing. An edge e in
    the complement of G can be inserted into D(G) if there exists a simple drawing
    of   G+e  extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing
    is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement
    of lines (pseudolines), then any edge in the complement of G can be inserted.
    In contrast, we show that it is   NP -complete to decide whether one edge can
    be inserted into a simple drawing. This remains true even if we assume that the
    drawing is pseudocircular, that is, the edges can be extended to an arrangement
    of pseudocircles. On the positive side, we show that, given an arrangement of
    pseudocircles   A  and a pseudosegment   σ , it can be decided in polynomial time
    whether there exists a pseudocircle   Φσ  extending   σ  for which   A∪{Φσ}  is
    again an arrangement of pseudocircles.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Alan M
  full_name: Arroyo Guevara, Alan M
  id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
  last_name: Arroyo Guevara
  orcid: 0000-0003-2401-8670
- first_name: Fabian
  full_name: Klute, Fabian
  last_name: Klute
- first_name: Irene
  full_name: Parada, Irene
  last_name: Parada
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Birgit
  full_name: Vogtenhuber, Birgit
  last_name: Vogtenhuber
- first_name: Tilo
  full_name: Wiedera, Tilo
  last_name: Wiedera
citation:
  ama: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T.
    Inserting one edge into a simple drawing is hard. In: <i>Graph-Theoretic Concepts
    in Computer Science</i>. Vol 12301. Springer Nature; 2020:325-338. doi:<a href="https://doi.org/10.1007/978-3-030-60440-0_26">10.1007/978-3-030-60440-0_26</a>'
  apa: 'Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B.,
    &#38; Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In
    <i>Graph-Theoretic Concepts in Computer Science</i> (Vol. 12301, pp. 325–338).
    Leeds, United Kingdom: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-60440-0_26">https://doi.org/10.1007/978-3-030-60440-0_26</a>'
  chicago: Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Raimund Seidel, Birgit
    Vogtenhuber, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.”
    In <i>Graph-Theoretic Concepts in Computer Science</i>, 12301:325–38. Springer
    Nature, 2020. <a href="https://doi.org/10.1007/978-3-030-60440-0_26">https://doi.org/10.1007/978-3-030-60440-0_26</a>.
  ieee: A. M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, and
    T. Wiedera, “Inserting one edge into a simple drawing is hard,” in <i>Graph-Theoretic
    Concepts in Computer Science</i>, Leeds, United Kingdom, 2020, vol. 12301, pp.
    325–338.
  ista: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T.
    2020. Inserting one edge into a simple drawing is hard. Graph-Theoretic Concepts
    in Computer Science. WG: Workshop on Graph-Theoretic Concepts in Computer Science,
    LNCS, vol. 12301, 325–338.'
  mla: Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is
    Hard.” <i>Graph-Theoretic Concepts in Computer Science</i>, vol. 12301, Springer
    Nature, 2020, pp. 325–38, doi:<a href="https://doi.org/10.1007/978-3-030-60440-0_26">10.1007/978-3-030-60440-0_26</a>.
  short: A.M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, T. Wiedera,
    in:, Graph-Theoretic Concepts in Computer Science, Springer Nature, 2020, pp.
    325–338.
conference:
  end_date: 2020-06-26
  location: Leeds, United Kingdom
  name: 'WG: Workshop on Graph-Theoretic Concepts in Computer Science'
  start_date: 2020-06-24
date_created: 2020-11-06T08:45:03Z
date_published: 2020-10-09T00:00:00Z
date_updated: 2026-04-16T10:22:35Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/978-3-030-60440-0_26
ec_funded: 1
external_id:
  isi:
  - '001299688100026'
intvolume: '     12301'
isi: 1
language:
- iso: eng
month: '10'
oa_version: None
page: 325-338
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: Graph-Theoretic Concepts in Computer Science
publication_identifier:
  eisbn:
  - '9783030604400'
  eissn:
  - 1611-3349
  isbn:
  - '9783030604394'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inserting one edge into a simple drawing is hard
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12301
year: '2020'
...
---
_id: '9308'
acknowledgement: This research was carried out with the support of the Russian Foundation
  for Basic Research(grant no. 19-01-00169)
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
- first_name: Isaac
  full_name: Mabillard, Isaac
  id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
  last_name: Mabillard
- first_name: A. B.
  full_name: Skopenkov, A. B.
  last_name: Skopenkov
citation:
  ama: Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. Eliminating higher-multiplicity
    intersections, III. Codimension 2. <i>Russian Mathematical Surveys</i>. 2020;75(6):1156-1158.
    doi:<a href="https://doi.org/10.1070/RM9943">10.1070/RM9943</a>
  apa: Avvakumov, S., Wagner, U., Mabillard, I., &#38; Skopenkov, A. B. (2020). Eliminating
    higher-multiplicity intersections, III. Codimension 2. <i>Russian Mathematical
    Surveys</i>. IOP Publishing. <a href="https://doi.org/10.1070/RM9943">https://doi.org/10.1070/RM9943</a>
  chicago: Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating
    Higher-Multiplicity Intersections, III. Codimension 2.” <i>Russian Mathematical
    Surveys</i>. IOP Publishing, 2020. <a href="https://doi.org/10.1070/RM9943">https://doi.org/10.1070/RM9943</a>.
  ieee: S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity
    intersections, III. Codimension 2,” <i>Russian Mathematical Surveys</i>, vol.
    75, no. 6. IOP Publishing, pp. 1156–1158, 2020.
  ista: Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. 2020. Eliminating higher-multiplicity
    intersections, III. Codimension 2. Russian Mathematical Surveys. 75(6), 1156–1158.
  mla: Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III.
    Codimension 2.” <i>Russian Mathematical Surveys</i>, vol. 75, no. 6, IOP Publishing,
    2020, pp. 1156–58, doi:<a href="https://doi.org/10.1070/RM9943">10.1070/RM9943</a>.
  short: S. Avvakumov, U. Wagner, I. Mabillard, A.B. Skopenkov, Russian Mathematical
    Surveys 75 (2020) 1156–1158.
date_created: 2021-04-04T22:01:22Z
date_published: 2020-12-01T00:00:00Z
date_updated: 2025-07-02T10:54:51Z
day: '01'
department:
- _id: UlWa
doi: 10.1070/RM9943
external_id:
  arxiv:
  - '1511.03501'
  isi:
  - '000625983100001'
intvolume: '        75'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1511.03501
month: '12'
oa: 1
oa_version: Preprint
page: 1156-1158
publication: Russian Mathematical Surveys
publication_identifier:
  issn:
  - 0036-0279
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
related_material:
  record:
  - id: '10220'
    relation: later_version
    status: public
  - id: '8183'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Eliminating higher-multiplicity intersections, III. Codimension 2
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 75
year: '2020'
...
---
_id: '6563'
abstract:
- lang: eng
  text: "This paper presents two algorithms. The first decides the existence of a
    pointed homotopy between given simplicial maps \U0001D453,\U0001D454:\U0001D44B→\U0001D44C,
    and the second computes the group [\U0001D6F4\U0001D44B,\U0001D44C]∗ 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 \U0001D434⊆\U0001D44B."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Marek
  full_name: Filakovský, Marek
  id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
  last_name: Filakovský
- first_name: Lukas
  full_name: Vokřínek, Lukas
  last_name: Vokřínek
citation:
  ama: Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint.
    <i>Foundations of Computational Mathematics</i>. 2020;20:311-330. doi:<a href="https://doi.org/10.1007/s10208-019-09419-x">10.1007/s10208-019-09419-x</a>
  apa: Filakovský, M., &#38; Vokřínek, L. (2020). Are two given maps homotopic? An
    algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. Springer
    Nature. <a href="https://doi.org/10.1007/s10208-019-09419-x">https://doi.org/10.1007/s10208-019-09419-x</a>
  chicago: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An
    Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>. Springer
    Nature, 2020. <a href="https://doi.org/10.1007/s10208-019-09419-x">https://doi.org/10.1007/s10208-019-09419-x</a>.
  ieee: M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic
    viewpoint,” <i>Foundations of Computational Mathematics</i>, vol. 20. Springer
    Nature, pp. 311–330, 2020.
  ista: Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic
    viewpoint. Foundations of Computational Mathematics. 20, 311–330.
  mla: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic
    Viewpoint.” <i>Foundations of Computational Mathematics</i>, vol. 20, Springer
    Nature, 2020, pp. 311–30, doi:<a href="https://doi.org/10.1007/s10208-019-09419-x">10.1007/s10208-019-09419-x</a>.
  short: M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020)
    311–330.
date_created: 2019-06-16T21:59:14Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2025-07-10T11:53:32Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s10208-019-09419-x
external_id:
  arxiv:
  - '1312.2337'
  isi:
  - '000522437400004'
intvolume: '        20'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1312.2337
month: '04'
oa: 1
oa_version: Preprint
page: 311-330
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
publication: Foundations of Computational Mathematics
publication_identifier:
  eissn:
  - 1615-3383
  issn:
  - 1615-3375
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Are two given maps homotopic? An algorithmic viewpoint
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 20
year: '2020'
...
---
_id: '5790'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Steven
  full_name: Chaplick, Steven
  last_name: Chaplick
- first_name: Radoslav
  full_name: Fulek, Radoslav
  id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
  last_name: Fulek
  orcid: 0000-0001-8485-1774
- first_name: Pavel
  full_name: Klavík, Pavel
  last_name: Klavík
citation:
  ama: Chaplick S, Fulek R, Klavík P. Extending partial representations of circle
    graphs. <i>Journal of Graph Theory</i>. 2019;91(4):365-394. doi:<a href="https://doi.org/10.1002/jgt.22436">10.1002/jgt.22436</a>
  apa: Chaplick, S., Fulek, R., &#38; Klavík, P. (2019). Extending partial representations
    of circle graphs. <i>Journal of Graph Theory</i>. Wiley. <a href="https://doi.org/10.1002/jgt.22436">https://doi.org/10.1002/jgt.22436</a>
  chicago: Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial
    Representations of Circle Graphs.” <i>Journal of Graph Theory</i>. Wiley, 2019.
    <a href="https://doi.org/10.1002/jgt.22436">https://doi.org/10.1002/jgt.22436</a>.
  ieee: S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of
    circle graphs,” <i>Journal of Graph Theory</i>, vol. 91, no. 4. Wiley, pp. 365–394,
    2019.
  ista: Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of
    circle graphs. Journal of Graph Theory. 91(4), 365–394.
  mla: Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.”
    <i>Journal of Graph Theory</i>, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:<a
    href="https://doi.org/10.1002/jgt.22436">10.1002/jgt.22436</a>.
  short: S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.
date_created: 2018-12-30T22:59:15Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2026-04-16T09:47:19Z
day: '01'
department:
- _id: UlWa
doi: 10.1002/jgt.22436
ec_funded: 1
external_id:
  arxiv:
  - '1309.2399'
  isi:
  - '000485392800004'
intvolume: '        91'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1309.2399
month: '08'
oa: 1
oa_version: Preprint
page: 365-394
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
publication: Journal of Graph Theory
publication_identifier:
  issn:
  - 0364-9024
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending partial representations of circle graphs
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 91
year: '2019'
...
---
_id: '5857'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
  full_name: Fulek, Radoslav
  id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
  last_name: Fulek
  orcid: 0000-0001-8485-1774
- first_name: János
  full_name: Pach, János
  last_name: Pach
citation:
  ama: 'Fulek R, Pach J. Thrackles: An improved upper bound. <i>Discrete Applied Mathematics</i>.
    2019;259(4):266-231. doi:<a href="https://doi.org/10.1016/j.dam.2018.12.025">10.1016/j.dam.2018.12.025</a>'
  apa: 'Fulek, R., &#38; Pach, J. (2019). Thrackles: An improved upper bound. <i>Discrete
    Applied Mathematics</i>. Elsevier. <a href="https://doi.org/10.1016/j.dam.2018.12.025">https://doi.org/10.1016/j.dam.2018.12.025</a>'
  chicago: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.”
    <i>Discrete Applied Mathematics</i>. Elsevier, 2019. <a href="https://doi.org/10.1016/j.dam.2018.12.025">https://doi.org/10.1016/j.dam.2018.12.025</a>.'
  ieee: 'R. Fulek and J. Pach, “Thrackles: An improved upper bound,” <i>Discrete Applied
    Mathematics</i>, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.'
  ista: 'Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied
    Mathematics. 259(4), 266–231.'
  mla: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” <i>Discrete
    Applied Mathematics</i>, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:<a
    href="https://doi.org/10.1016/j.dam.2018.12.025">10.1016/j.dam.2018.12.025</a>.'
  short: R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.
date_created: 2019-01-20T22:59:17Z
date_published: 2019-04-30T00:00:00Z
date_updated: 2026-04-16T09:48:11Z
day: '30'
department:
- _id: UlWa
doi: 10.1016/j.dam.2018.12.025
external_id:
  arxiv:
  - '1708.08037'
  isi:
  - '000466061100020'
intvolume: '       259'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1708.08037
month: '04'
oa: 1
oa_version: Preprint
page: 266-231
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02281
  name: Eliminating intersections in drawings of graphs
publication: Discrete Applied Mathematics
publication_identifier:
  issn:
  - 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '433'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: 'Thrackles: An improved upper bound'
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 259
year: '2019'
...
---
_id: '5986'
abstract:
- lang: eng
  text: "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 \U0001D442(\U0001D45B8)
    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 \U0001D442(\U0001D45B7) 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."
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Anna
  full_name: Lubiw, Anna
  last_name: Lubiw
- first_name: Zuzana
  full_name: Masárová, Zuzana
  id: 45CFE238-F248-11E8-B48F-1D18A9856A87
  last_name: Masárová
  orcid: 0000-0002-6660-1322
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping
    edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. 2019;61(4):880-898.
    doi:<a href="https://doi.org/10.1007/s00454-018-0035-8">10.1007/s00454-018-0035-8</a>
  apa: Lubiw, A., Masárová, Z., &#38; Wagner, U. (2019). A proof of the orbit conjecture
    for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00454-018-0035-8">https://doi.org/10.1007/s00454-018-0035-8</a>
  chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
    for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>.
    Springer Nature, 2019. <a href="https://doi.org/10.1007/s00454-018-0035-8">https://doi.org/10.1007/s00454-018-0035-8</a>.
  ieee: A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for
    flipping edge-labelled triangulations,” <i>Discrete &#38; Computational Geometry</i>,
    vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.
  ista: Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping
    edge-labelled triangulations. Discrete &#38; Computational Geometry. 61(4), 880–898.
  mla: Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled
    Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4,
    Springer Nature, 2019, pp. 880–98, doi:<a href="https://doi.org/10.1007/s00454-018-0035-8">10.1007/s00454-018-0035-8</a>.
  short: A. Lubiw, Z. Masárová, U. Wagner, Discrete &#38; Computational Geometry 61
    (2019) 880–898.
corr_author: '1'
date_created: 2019-02-14T11:54:08Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2026-04-08T07:23:01Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
external_id:
  arxiv:
  - '1710.02741'
  isi:
  - '000466130000009'
file:
- access_level: open_access
  checksum: e1bff88f1d77001b53b78c485ce048d7
  content_type: application/pdf
  creator: dernst
  date_created: 2019-02-14T11:57:22Z
  date_updated: 2020-07-14T12:47:14Z
  file_id: '5988'
  file_name: 2018_DiscreteGeometry_Lubiw.pdf
  file_size: 556276
  relation: main_file
file_date_updated: 2020-07-14T12:47:14Z
has_accepted_license: '1'
intvolume: '        61'
isi: 1
issue: '4'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 880-898
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '683'
    relation: earlier_version
    status: public
  - id: '7944'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: A proof of the orbit conjecture for flipping edge-labelled triangulations
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 61
year: '2019'
...
---
_id: '7950'
abstract:
- lang: eng
  text: "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:\r\n1.  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.\r\n2.  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.\r\n3.  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."
article_number: '1903.06981'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ahmad
  full_name: Biniaz, Ahmad
  last_name: Biniaz
- first_name: Kshitij
  full_name: Jain, Kshitij
  last_name: Jain
- first_name: Anna
  full_name: Lubiw, Anna
  last_name: Lubiw
- first_name: Zuzana
  full_name: Masárová, Zuzana
  id: 45CFE238-F248-11E8-B48F-1D18A9856A87
  last_name: Masárová
  orcid: 0000-0002-6660-1322
- first_name: Tillmann
  full_name: Miltzow, Tillmann
  last_name: Miltzow
- first_name: Debajyoti
  full_name: Mondal, Debajyoti
  last_name: Mondal
- first_name: Anurag Murty
  full_name: Naredla, Anurag Murty
  last_name: Naredla
- first_name: Josef
  full_name: Tkadlec, Josef
  id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
  last_name: Tkadlec
  orcid: 0000-0002-1097-9684
- first_name: Alexi
  full_name: Turcotte, Alexi
  last_name: Turcotte
citation:
  ama: Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>arXiv</i>. doi:<a
    href="https://doi.org/10.48550/arXiv.1903.06981">10.48550/arXiv.1903.06981</a>
  apa: Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte,
    A. (n.d.). Token swapping on trees. <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.1903.06981">https://doi.org/10.48550/arXiv.1903.06981</a>
  chicago: Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow,
    Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token
    Swapping on Trees.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.1903.06981">https://doi.org/10.48550/arXiv.1903.06981</a>.
  ieee: A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>arXiv</i>. .
  ista: Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec
    J, Turcotte A. Token swapping on trees. arXiv, 1903.06981.
  mla: Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>ArXiv</i>, 1903.06981,
    doi:<a href="https://doi.org/10.48550/arXiv.1903.06981">10.48550/arXiv.1903.06981</a>.
  short: A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla,
    J. Tkadlec, A. Turcotte, ArXiv (n.d.).
date_created: 2020-06-08T12:25:25Z
date_published: 2019-03-16T00:00:00Z
date_updated: 2026-04-08T07:23:00Z
day: '16'
department:
- _id: HeEd
- _id: UlWa
- _id: KrCh
doi: 10.48550/arXiv.1903.06981
external_id:
  arxiv:
  - '1903.06981'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1903.06981
month: '03'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: draft
related_material:
  record:
  - id: '12833'
    relation: later_version
    status: public
  - id: '7944'
    relation: dissertation_contains
    status: public
status: public
title: Token swapping on trees
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '8182'
abstract:
- lang: eng
  text: "Suppose that $n\\neq p^k$ and $n\\neq 2p^k$ for all $k$ and all primes $p$.
    We prove that for any Hausdorff compactum $X$ with a free action of the symmetric
    group $\\mathfrak S_n$ there exists an $\\mathfrak S_n$-equivariant map $X \\to\r\n{\\mathbb
    R}^n$ whose image avoids the diagonal $\\{(x,x\\dots,x)\\in {\\mathbb R}^n|x\\in
    {\\mathbb R}\\}$.\r\n  Previously, the special cases of this statement for certain
    $X$ were usually proved using the equivartiant obstruction theory. Such calculations
    are difficult and may become infeasible past the first (primary) obstruction.
    We\r\ntake a different approach which allows us to prove the vanishing of all
    obstructions simultaneously. The essential step in the proof is classifying the
    possible degrees of $\\mathfrak S_n$-equivariant maps from the boundary\r\n$\\partial\\Delta^{n-1}$
    of $(n-1)$-simplex to itself.  Existence of equivariant maps between spaces is
    important for many questions arising from discrete mathematics and geometry, such
    as Kneser's conjecture, the Square Peg conjecture, the Splitting Necklace problem,
    and the Topological Tverberg conjecture, etc. We demonstrate the utility of our
    result  applying it to one such question, a specific instance of envy-free division
    problem."
article_number: '1910.12628'
article_processing_charge: No
arxiv: 1
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: Sergey
  full_name: Kudrya, Sergey
  id: ecf01965-d252-11ea-95a5-8ada5f6c6a67
  last_name: Kudrya
citation:
  ama: Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping
    degree. <i>arXiv</i>. doi:<a href="https://doi.org/10.48550/arXiv.1910.12628">10.48550/arXiv.1910.12628</a>
  apa: Avvakumov, S., &#38; Kudrya, S. (n.d.). Vanishing of all equivariant obstructions
    and the mapping degree. <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.1910.12628">https://doi.org/10.48550/arXiv.1910.12628</a>
  chicago: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
    and the Mapping Degree.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.1910.12628">https://doi.org/10.48550/arXiv.1910.12628</a>.
  ieee: S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and
    the mapping degree,” <i>arXiv</i>. .
  ista: Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping
    degree. arXiv, 1910.12628.
  mla: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
    and the Mapping Degree.” <i>ArXiv</i>, 1910.12628, doi:<a href="https://doi.org/10.48550/arXiv.1910.12628">10.48550/arXiv.1910.12628</a>.
  short: S. Avvakumov, S. Kudrya, ArXiv (n.d.).
corr_author: '1'
date_created: 2020-07-30T10:45:08Z
date_published: 2019-10-28T00:00:00Z
date_updated: 2026-04-08T07:25:54Z
day: '28'
department:
- _id: UlWa
doi: 10.48550/arXiv.1910.12628
external_id:
  arxiv:
  - '1910.12628'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1910.12628
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
publication: arXiv
publication_status: draft
related_material:
  record:
  - id: '11446'
    relation: later_version
    status: public
  - id: '8156'
    relation: dissertation_contains
    status: public
status: public
title: Vanishing of all equivariant obstructions and the mapping degree
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '8184'
abstract:
- lang: eng
  text: "Denote by ∆N the N-dimensional simplex. A map f : ∆N → Rd is an almost r-embedding
    if fσ1∩. . .∩fσr = ∅ whenever σ1, . . . , σr are pairwise disjoint faces. A counterexample
    to the topological Tverberg conjecture asserts that if r is not a prime power
    and d ≥ 2r + 1, then there is an almost r-embedding ∆(d+1)(r−1) → Rd. This was
    improved by Blagojevi´c–Frick–Ziegler using a simple construction of higher-dimensional
    counterexamples by taking k-fold join power of lower-dimensional ones. We improve
    this further (for d large compared to r): If r is not a prime power and N := (d+
    1)r−r l\r\nd + 2 r + 1 m−2, then there is an almost r-embedding ∆N → Rd. For the
    r-fold van Kampen–Flores conjecture we also produce counterexamples which are
    stronger than previously known. Our proof is based on generalizations of the Mabillard–Wagner
    theorem on construction of almost r-embeddings from equivariant maps, and of the
    Ozaydin theorem on existence of equivariant maps. "
acknowledgement: We would like to thank F. Frick for helpful discussions
article_number: '1908.08731'
article_processing_charge: No
arxiv: 1
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: R.
  full_name: Karasev, R.
  last_name: Karasev
- first_name: A.
  full_name: Skopenkov, A.
  last_name: Skopenkov
citation:
  ama: Avvakumov S, Karasev R, Skopenkov A. Stronger counterexamples to the topological
    Tverberg conjecture. <i>arXiv</i>. doi:<a href="https://doi.org/10.48550/arXiv.1908.08731">10.48550/arXiv.1908.08731</a>
  apa: Avvakumov, S., Karasev, R., &#38; Skopenkov, A. (n.d.). Stronger counterexamples
    to the topological Tverberg conjecture. <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.1908.08731">https://doi.org/10.48550/arXiv.1908.08731</a>
  chicago: Avvakumov, Sergey, R. Karasev, and A. Skopenkov. “Stronger Counterexamples
    to the Topological Tverberg Conjecture.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.1908.08731">https://doi.org/10.48550/arXiv.1908.08731</a>.
  ieee: S. Avvakumov, R. Karasev, and A. Skopenkov, “Stronger counterexamples to the
    topological Tverberg conjecture,” <i>arXiv</i>. .
  ista: Avvakumov S, Karasev R, Skopenkov A. Stronger counterexamples to the topological
    Tverberg conjecture. arXiv, 1908.08731.
  mla: Avvakumov, Sergey, et al. “Stronger Counterexamples to the Topological Tverberg
    Conjecture.” <i>ArXiv</i>, 1908.08731, doi:<a href="https://doi.org/10.48550/arXiv.1908.08731">10.48550/arXiv.1908.08731</a>.
  short: S. Avvakumov, R. Karasev, A. Skopenkov, ArXiv (n.d.).
date_created: 2020-07-30T10:45:34Z
date_published: 2019-08-23T00:00:00Z
date_updated: 2026-04-08T07:25:54Z
day: '23'
department:
- _id: UlWa
doi: 10.48550/arXiv.1908.08731
external_id:
  arxiv:
  - '1908.08731'
  isi:
  - '000986519600004'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1908.08731
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
publication: arXiv
publication_status: draft
related_material:
  record:
  - id: '8156'
    relation: dissertation_contains
    status: public
status: public
title: Stronger counterexamples to the topological Tverberg conjecture
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '8185'
abstract:
- lang: eng
  text: "In this paper we study envy-free division problems. The classical approach
    to some of such problems, used by David Gale, reduces to considering continuous
    maps of a simplex to itself and finding sufficient conditions when this map hits
    the center of the simplex. The mere continuity is not sufficient for such a conclusion,
    the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and
    the Gale theorem) is a certain boundary condition.\r\n  We follow Erel Segal-Halevi,
    Fr\\'ed\\'eric Meunier, and Shira Zerbib, and replace the boundary condition by
    another assumption, which has the economic meaning of possibility for a player
    to prefer an empty part in the segment\r\npartition problem. We solve the problem
    positively when $n$, the number of players that divide the segment, is a prime
    power, and we provide counterexamples for every $n$ which is not a prime power.
    We also provide counterexamples relevant to a wider class of fair or envy-free
    partition problems when $n$ is odd and not a prime power."
article_number: '1907.11183'
article_processing_charge: No
arxiv: 1
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: Roman
  full_name: Karasev, Roman
  last_name: Karasev
citation:
  ama: Avvakumov S, Karasev R. Envy-free division using mapping degree. <i>arXiv</i>.
    doi:<a href="https://doi.org/10.48550/arXiv.1907.11183">10.48550/arXiv.1907.11183</a>
  apa: Avvakumov, S., &#38; Karasev, R. (n.d.). Envy-free division using mapping degree.
    <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.1907.11183">https://doi.org/10.48550/arXiv.1907.11183</a>
  chicago: Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping
    Degree.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.1907.11183">https://doi.org/10.48550/arXiv.1907.11183</a>.
  ieee: S. Avvakumov and R. Karasev, “Envy-free division using mapping degree,” <i>arXiv</i>.
    .
  ista: Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv, 1907.11183.
  mla: Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.”
    <i>ArXiv</i>, 1907.11183, doi:<a href="https://doi.org/10.48550/arXiv.1907.11183">10.48550/arXiv.1907.11183</a>.
  short: S. Avvakumov, R. Karasev, ArXiv (n.d.).
corr_author: '1'
date_created: 2020-07-30T10:45:51Z
date_published: 2019-07-25T00:00:00Z
date_updated: 2026-04-08T07:25:54Z
day: '25'
department:
- _id: UlWa
doi: 10.48550/arXiv.1907.11183
external_id:
  arxiv:
  - '1907.11183'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1907.11183
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
publication: arXiv
publication_status: draft
related_material:
  link:
  - relation: later_version
    url: https://doi.org/10.1112/mtk.12059
  record:
  - id: '8156'
    relation: dissertation_contains
    status: public
status: public
title: Envy-free division using mapping degree
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6556'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Kristóf
  full_name: Huszár, Kristóf
  id: 33C26278-F248-11E8-B48F-1D18A9856A87
  last_name: Huszár
  orcid: 0000-0002-5445-5057
- first_name: Jonathan
  full_name: Spreer, Jonathan
  last_name: Spreer
citation:
  ama: 'Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: <i>35th
    International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">10.4230/LIPIcs.SoCG.2019.44</a>'
  apa: 'Huszár, K., &#38; Spreer, J. (2019). 3-manifold triangulations with small
    treewidth. In <i>35th International Symposium on Computational Geometry</i> (Vol.
    129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>'
  chicago: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
    Treewidth.” In <i>35th International Symposium on Computational Geometry</i>,
    129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>.
  ieee: K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,”
    in <i>35th International Symposium on Computational Geometry</i>, Portland, Oregon,
    United States, 2019, vol. 129, p. 44:1-44:20.
  ista: 'Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth.
    35th International Symposium on Computational Geometry. SoCG: Symposium on Computational
    Geometry, LIPIcs, vol. 129, 44:1-44:20.'
  mla: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
    Treewidth.” <i>35th International Symposium on Computational Geometry</i>, vol.
    129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:<a
    href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">10.4230/LIPIcs.SoCG.2019.44</a>.
  short: K. Huszár, J. Spreer, in:, 35th International Symposium on Computational
    Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.
conference:
  end_date: 2019-06-21
  location: Portland, Oregon, United States
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2019-06-18
corr_author: '1'
date_created: 2019-06-11T20:09:57Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2026-04-08T07:21:27Z
day: '01'
ddc:
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2019.44
external_id:
  arxiv:
  - '1812.05528'
file:
- access_level: open_access
  checksum: 29d18c435368468aa85823dabb157e43
  content_type: application/pdf
  creator: kschuh
  date_created: 2019-06-12T06:45:33Z
  date_updated: 2020-07-14T12:47:33Z
  file_id: '6557'
  file_name: 2019_LIPIcs-Huszar.pdf
  file_size: 905885
  relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: '       129'
keyword:
- computational 3-manifold topology
- fixed-parameter tractability
- layered triangulations
- structural graph theory
- treewidth
- cutwidth
- Heegaard genus
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 44:1-44:20
publication: 35th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - 978-3-95977-104-7
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '8032'
    relation: part_of_dissertation
    status: public
scopus_import: '1'
status: public
title: 3-manifold triangulations with small treewidth
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...
---
_id: '6638'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: 'André '
  full_name: 'Silva, André '
  last_name: Silva
- first_name: Alan M
  full_name: Arroyo Guevara, Alan M
  id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
  last_name: Arroyo Guevara
  orcid: 0000-0003-2401-8670
- first_name: Bruce
  full_name: Richter, Bruce
  last_name: Richter
- first_name: Orlando
  full_name: Lee, Orlando
  last_name: Lee
citation:
  ama: Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing.
    <i>Discrete Mathematics</i>. 2019;342(11):3201-3207. doi:<a href="https://doi.org/10.1016/j.disc.2019.06.031">10.1016/j.disc.2019.06.031</a>
  apa: Silva, A., Arroyo Guevara, A. M., Richter, B., &#38; Lee, O. (2019). Graphs
    with at most one crossing. <i>Discrete Mathematics</i>. Elsevier. <a href="https://doi.org/10.1016/j.disc.2019.06.031">https://doi.org/10.1016/j.disc.2019.06.031</a>
  chicago: Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs
    with at Most One Crossing.” <i>Discrete Mathematics</i>. Elsevier, 2019. <a href="https://doi.org/10.1016/j.disc.2019.06.031">https://doi.org/10.1016/j.disc.2019.06.031</a>.
  ieee: A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most
    one crossing,” <i>Discrete Mathematics</i>, vol. 342, no. 11. Elsevier, pp. 3201–3207,
    2019.
  ista: Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one
    crossing. Discrete Mathematics. 342(11), 3201–3207.
  mla: Silva, André, et al. “Graphs with at Most One Crossing.” <i>Discrete Mathematics</i>,
    vol. 342, no. 11, Elsevier, 2019, pp. 3201–07, doi:<a href="https://doi.org/10.1016/j.disc.2019.06.031">10.1016/j.disc.2019.06.031</a>.
  short: A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics 342
    (2019) 3201–3207.
date_created: 2019-07-14T21:59:20Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2025-04-14T07:44:06Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.disc.2019.06.031
ec_funded: 1
external_id:
  arxiv:
  - '1901.09955'
  isi:
  - '000486358100025'
intvolume: '       342'
isi: 1
issue: '11'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1901.09955
month: '11'
oa: 1
oa_version: Preprint
page: 3201-3207
project:
- _id: 26366136-B435-11E9-9278-68D0E5697425
  name: Reglas de Conectividad funcional en el hipocampo
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: Discrete Mathematics
publication_identifier:
  issn:
  - 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Graphs with at most one crossing
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 342
year: '2019'
...