---
_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: 36th International Symposium on Computational
Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020.
doi:10.4230/LIPIcs.SoCG.2020.67'
apa: 'Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs
in the plane (Part II: Bistellar flips). In 36th International Symposium on
Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.67'
chicago: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane (Part II: Bistellar Flips).” In 36th International Symposium on
Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.67.'
ieee: 'U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane (Part II: Bistellar flips),” in 36th International Symposium on Computational
Geometry, 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).” 36th International Symposium on Computational
Geometry, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020, doi:10.4230/LIPIcs.SoCG.2020.67.'
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
date_created: 2020-06-22T09:14:19Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-08-04T08:51:07Z
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:
- '18688969'
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
- 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: 36th International Symposium on Computational Geometry. Vol 164.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.12'
apa: 'Avvakumov, S., & Nivasch, G. (2020). Homotopic curve shortening and the
affine curve-shortening flow. In 36th International Symposium on Computational
Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.12'
chicago: Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and
the Affine Curve-Shortening Flow.” In 36th International Symposium on Computational
Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
https://doi.org/10.4230/LIPIcs.SoCG.2020.12.
ieee: S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening
flow,” in 36th International Symposium on Computational Geometry, 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.” 36th International Symposium on Computational
Geometry, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020, doi:10.4230/LIPIcs.SoCG.2020.12.
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: 2021-01-12T08:16:23Z
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
license: https://creativecommons.org/licenses/by/3.0/
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:
- '18688969'
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:
36th International Symposium on Computational Geometry. Vol 164. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.62'
apa: 'Patakova, Z., Tancer, M., & Wagner, U. (2020). Barycentric cuts through
a convex body. In 36th International Symposium on Computational Geometry
(Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2020.62'
chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
a Convex Body.” In 36th International Symposium on Computational Geometry,
Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.62.
ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
body,” in 36th International Symposium on Computational Geometry, 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.” 36th
International Symposium on Computational Geometry, vol. 164, 62:1-62:16, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.62.
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
date_created: 2020-06-22T09:14:20Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2021-01-12T08:16:23Z
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:
- '18688969'
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: 36th International Symposium on Computational
Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020.
doi:10.4230/LIPIcs.SoCG.2020.9'
apa: 'Arroyo Guevara, A. M., Bensmail, J., & Bruce Richter, R. (2020). Extending
drawings of graphs to arrangements of pseudolines. In 36th International Symposium
on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.9'
chicago: Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending
Drawings of Graphs to Arrangements of Pseudolines.” In 36th International Symposium
on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.9.
ieee: A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings
of graphs to arrangements of pseudolines,” in 36th International Symposium
on Computational Geometry, 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.” 36th International Symposium on Computational Geometry,
vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.9.
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
date_created: 2020-06-22T09:14:21Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-02-23T13:22:12Z
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:
- '18688969'
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'
...
---
_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:10.15479/AT:ISTA:8032
apa: Huszár, K. (2020). Combinatorial width parameters for 3-dimensional manifolds.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8032
chicago: Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.”
Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8032.
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. Combinatorial Width Parameters for 3-Dimensional Manifolds.
Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8032.
short: K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute
of Science and Technology Austria, 2020.
date_created: 2020-06-26T10:00:36Z
date_published: 2020-06-26T00:00:00Z
date_updated: 2023-09-07T13:18:27Z
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_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
citation:
ama: Avvakumov S. Topological methods in geometry and discrete mathematics. 2020.
doi:10.15479/AT:ISTA:8156
apa: Avvakumov, S. (2020). Topological methods in geometry and discrete mathematics.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8156
chicago: Avvakumov, Sergey. “Topological Methods in Geometry and Discrete Mathematics.”
Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8156.
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. Topological Methods in Geometry and Discrete Mathematics.
Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8156.
short: S. Avvakumov, Topological Methods in Geometry and Discrete Mathematics, Institute
of Science and Technology Austria, 2020.
date_created: 2020-07-23T09:51:29Z
date_published: 2020-07-24T00:00:00Z
date_updated: 2023-12-18T10:51:01Z
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: '8183'
relation: part_of_dissertation
status: public
- id: '8185'
relation: part_of_dissertation
status: public
- id: '8184'
relation: part_of_dissertation
status: public
- id: '6355'
relation: part_of_dissertation
status: public
- id: '75'
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
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: Graph-Theoretic Concepts
in Computer Science. Vol 12301. Springer Nature; 2020:325-338. doi:10.1007/978-3-030-60440-0_26'
apa: 'Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B.,
& Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In
Graph-Theoretic Concepts in Computer Science (Vol. 12301, pp. 325–338).
Leeds, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-60440-0_26'
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 Graph-Theoretic Concepts in Computer Science, 12301:325–38. Springer
Nature, 2020. https://doi.org/10.1007/978-3-030-60440-0_26.
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 Graph-Theoretic
Concepts in Computer Science, 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.” Graph-Theoretic Concepts in Computer Science, vol. 12301, Springer
Nature, 2020, pp. 325–38, doi:10.1007/978-3-030-60440-0_26.
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: 2023-09-05T15:09:16Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/978-3-030-60440-0_26
ec_funded: 1
intvolume: ' 12301'
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:
eissn:
- 1611-3349
isbn:
- '9783030604394'
- '9783030604400'
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12301
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.
Foundations of Computational Mathematics. 2020;20:311-330. doi:10.1007/s10208-019-09419-x
apa: Filakovský, M., & Vokřínek, L. (2020). Are two given maps homotopic? An
algorithmic viewpoint. Foundations of Computational Mathematics. Springer
Nature. https://doi.org/10.1007/s10208-019-09419-x
chicago: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An
Algorithmic Viewpoint.” Foundations of Computational Mathematics. Springer
Nature, 2020. https://doi.org/10.1007/s10208-019-09419-x.
ieee: M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic
viewpoint,” Foundations of Computational Mathematics, 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.” Foundations of Computational Mathematics, vol. 20, Springer
Nature, 2020, pp. 311–30, doi:10.1007/s10208-019-09419-x.
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: 2023-08-17T13:50:44Z
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:
- '16153383'
issn:
- '16153375'
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 20
year: '2020'
...
---
_id: '15082'
abstract:
- lang: eng
text: "Two plane drawings of geometric graphs on the same set of points are called
disjoint compatible if their union is plane and they do not have an edge in common.
For a given set S of 2n points two plane drawings of perfect matchings M1 and
M2 (which do not need to be disjoint nor compatible) are disjoint tree-compatible
if there exists a plane drawing of a spanning tree T on S which is disjoint compatible
to both M1 and M2.\r\nWe show that the graph of all disjoint tree-compatible perfect
geometric matchings on 2n points in convex position is connected if and only if
2n ≥ 10. Moreover, in that case the diameter\r\nof this graph is either 4 or 5,
independent of n."
acknowledgement: Research on this work was initiated at the 6th Austrian-Japanese-Mexican-Spanish
Workshop on Discrete Geometry and continued during the 16th European Geometric Graph-Week,
both held near Strobl, Austria. We are grateful to the participants for the inspiring
atmosphere. We especially thank Alexander Pilz for bringing this class of problems
to our attention and Birgit Vogtenhuber for inspiring discussions. D.P. is partially
supported by the FWF grant I 3340-N35 (Collaborative DACH project Arrangements and
Drawings). The research stay of P.P. 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. This project
has received funding from the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No 734922.
article_number: '56'
article_processing_charge: No
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Julia
full_name: Obmann, Julia
last_name: Obmann
- first_name: Pavel
full_name: Patak, Pavel
id: B593B804-1035-11EA-B4F1-947645A5BB83
last_name: Patak
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
citation:
ama: 'Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. Disjoint tree-compatible
plane perfect matchings. In: 36th European Workshop on Computational Geometry.
; 2020.'
apa: Aichholzer, O., Obmann, J., Patak, P., Perz, D., & Tkadlec, J. (2020).
Disjoint tree-compatible plane perfect matchings. In 36th European Workshop
on Computational Geometry. Würzburg, Germany, Virtual.
chicago: Aichholzer, Oswin, Julia Obmann, Pavel Patak, Daniel Perz, and Josef Tkadlec.
“Disjoint Tree-Compatible Plane Perfect Matchings.” In 36th European Workshop
on Computational Geometry, 2020.
ieee: O. Aichholzer, J. Obmann, P. Patak, D. Perz, and J. Tkadlec, “Disjoint tree-compatible
plane perfect matchings,” in 36th European Workshop on Computational Geometry,
Würzburg, Germany, Virtual, 2020.
ista: 'Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. 2020. Disjoint tree-compatible
plane perfect matchings. 36th European Workshop on Computational Geometry. EuroCG:
European Workshop on Computational Geometry, 56.'
mla: Aichholzer, Oswin, et al. “Disjoint Tree-Compatible Plane Perfect Matchings.”
36th European Workshop on Computational Geometry, 56, 2020.
short: O. Aichholzer, J. Obmann, P. Patak, D. Perz, J. Tkadlec, in:, 36th European
Workshop on Computational Geometry, 2020.
conference:
end_date: 2020-03-18
location: Würzburg, Germany, Virtual
name: 'EuroCG: European Workshop on Computational Geometry'
start_date: 2020-03-16
date_created: 2024-03-05T08:57:17Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2024-03-05T09:00:07Z
day: '01'
department:
- _id: KrCh
- _id: UlWa
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_56.pdf
month: '04'
oa: 1
oa_version: Published Version
publication: 36th European Workshop on Computational Geometry
publication_status: published
quality_controlled: '1'
status: public
title: Disjoint tree-compatible plane perfect matchings
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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
- 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. Russian Mathematical Surveys. 2020;75(6):1156-1158.
doi:10.1070/RM9943
apa: Avvakumov, S., Wagner, U., Mabillard, I., & Skopenkov, A. B. (2020). Eliminating
higher-multiplicity intersections, III. Codimension 2. Russian Mathematical
Surveys. IOP Publishing. https://doi.org/10.1070/RM9943
chicago: Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating
Higher-Multiplicity Intersections, III. Codimension 2.” Russian Mathematical
Surveys. IOP Publishing, 2020. https://doi.org/10.1070/RM9943.
ieee: S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity
intersections, III. Codimension 2,” Russian Mathematical Surveys, 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.” Russian Mathematical Surveys, vol. 75, no. 6, IOP Publishing,
2020, pp. 1156–58, doi:10.1070/RM9943.
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: 2023-08-14T11:43:54Z
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: '8183'
relation: earlier_version
status: public
- id: '10220'
relation: later_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: '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. arXiv.
apa: Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte,
A. (n.d.). Token swapping on trees. arXiv.
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.” ArXiv, n.d.
ieee: A. Biniaz et al., “Token swapping on trees,” arXiv. .
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.” ArXiv, 1903.06981.
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: 2024-01-04T12:42:08Z
day: '16'
department:
- _id: HeEd
- _id: UlWa
- _id: KrCh
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: submitted
related_material:
record:
- id: '7944'
relation: dissertation_contains
status: public
- id: '12833'
relation: later_version
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
- 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. arXiv.
apa: Avvakumov, S., & Kudrya, S. (n.d.). Vanishing of all equivariant obstructions
and the mapping degree. arXiv. arXiv.
chicago: Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions
and the Mapping Degree.” ArXiv. arXiv, n.d.
ieee: S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and
the mapping degree,” arXiv. arXiv.
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.” ArXiv, 1910.12628, arXiv.
short: S. Avvakumov, S. Kudrya, ArXiv (n.d.).
date_created: 2020-07-30T10:45:08Z
date_published: 2019-10-28T00:00:00Z
date_updated: 2023-09-07T13:12:17Z
day: '28'
department:
- _id: UlWa
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: submitted
publisher: arXiv
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
- 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. arXiv.
apa: Avvakumov, S., Karasev, R., & Skopenkov, A. (n.d.). Stronger counterexamples
to the topological Tverberg conjecture. arXiv. arXiv.
chicago: Avvakumov, Sergey, R. Karasev, and A. Skopenkov. “Stronger Counterexamples
to the Topological Tverberg Conjecture.” ArXiv. arXiv, n.d.
ieee: S. Avvakumov, R. Karasev, and A. Skopenkov, “Stronger counterexamples to the
topological Tverberg conjecture,” arXiv. arXiv.
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.” ArXiv, 1908.08731, arXiv.
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: 2023-09-08T11:20:02Z
day: '23'
department:
- _id: UlWa
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: submitted
publisher: arXiv
related_material:
record:
- id: '8156'
relation: dissertation_contains
status: public
status: public
title: Stronger counterexamples to the topological Tverberg conjecture
type: preprint
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
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
- first_name: Roman
full_name: Karasev, Roman
last_name: Karasev
citation:
ama: Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv.
doi:10.48550/arXiv.1907.11183
apa: Avvakumov, S., & Karasev, R. (n.d.). Envy-free division using mapping degree.
arXiv. https://doi.org/10.48550/arXiv.1907.11183
chicago: Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping
Degree.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1907.11183.
ieee: S. Avvakumov and R. Karasev, “Envy-free division using mapping degree,” arXiv.
.
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.”
ArXiv, 1907.11183, doi:10.48550/arXiv.1907.11183.
short: S. Avvakumov, R. Karasev, ArXiv (n.d.).
date_created: 2020-07-30T10:45:51Z
date_published: 2019-07-25T00:00:00Z
date_updated: 2023-09-07T13:12:17Z
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: submitted
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: '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.
Discrete Mathematics. 2019;342(11):3201-3207. doi:10.1016/j.disc.2019.06.031
apa: Silva, A., Arroyo Guevara, A. M., Richter, B., & Lee, O. (2019). Graphs
with at most one crossing. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2019.06.031
chicago: Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs
with at Most One Crossing.” Discrete Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.disc.2019.06.031.
ieee: A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most
one crossing,” Discrete Mathematics, 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.” Discrete Mathematics,
vol. 342, no. 11, Elsevier, 2019, pp. 3201–07, doi:10.1016/j.disc.2019.06.031.
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: 2023-08-29T06:31:41Z
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'
...
---
_id: '6647'
abstract:
- lang: eng
text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states
that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition
X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r,
all share a common point. In this paper, we prove a strengthening of this theorem
that guarantees a partition which, in addition to the above, has the property
that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections.
Possible generalizations and algorithmic aspects are also discussed. As a concrete
application, we show that any n points in the plane in general position span floor[n/3]
vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries
have pairwise nonempty intersections; this number is clearly best possible. A
previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing
triangles. Our result generalizes to a result about simplices in R^d,d >=2.
alternative_title:
- LIPIcs
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: Bernd
full_name: Gärtner, Bernd
last_name: Gärtner
- first_name: Andrey
full_name: Kupavskii, Andrey
last_name: Kupavskii
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg
theorem. In: 35th International Symposium on Computational Geometry. Vol
129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38'
apa: 'Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019).
The crossing Tverberg theorem. In 35th International Symposium on Computational
Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38'
chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on
Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38.
ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
Tverberg theorem,” in 35th International Symposium on Computational Geometry,
Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.
ista: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg
theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium
on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.'
mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International
Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.
short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International
Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019, p. 38:1-38:13.
conference:
end_date: 2019-06-21
location: Portland, OR, United States
name: 'SoCG 2019: Symposium on Computational Geometry'
start_date: 2019-06-18
date_created: 2019-07-17T10:35:04Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-12-13T12:03:35Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.38
external_id:
arxiv:
- '1812.04911'
file:
- access_level: open_access
checksum: d6d017f8b41291b94d102294fa96ae9c
content_type: application/pdf
creator: dernst
date_created: 2019-07-24T06:54:52Z
date_updated: 2020-07-14T12:47:35Z
file_id: '6667'
file_name: 2019_LIPICS_Fulek.pdf
file_size: 559837
relation: main_file
file_date_updated: 2020-07-14T12:47:35Z
has_accepted_license: '1'
intvolume: ' 129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 38:1-38:13
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771047'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '13974'
relation: later_version
status: public
scopus_import: 1
status: public
title: The crossing Tverberg theorem
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: '6681'
abstract:
- lang: eng
text: "The first part of the thesis considers the computational aspects of the homotopy
groups πd(X) of a topological space X. It is well known that there is no algorithm
to decide whether the fundamental group π1(X) of a given finite simplicial complex
X is trivial. On the other hand, there are several algorithms that, given a finite
simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute
the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms
come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract
finitely generated abelian group given by generators and relations, but they work
with very implicit representations of the elements of πd(X). We present an algorithm
that, given a simply connected space X, computes πd(X) and represents its elements
as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed
d, the algorithm runs in time exponential in size(X), the number of simplices
of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct
a family of simply connected spaces X such that for any simplicial map representing
a generator of πd(X), the size of the triangulation of S d on which the map is
defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove
that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋,
k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable
range: Given a finite simplicial complex K of dimension k, decide whether there
exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of
K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Stephan Y
full_name: Zhechev, Stephan Y
id: 3AA52972-F248-11E8-B48F-1D18A9856A87
last_name: Zhechev
citation:
ama: Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019.
doi:10.15479/AT:ISTA:6681
apa: Zhechev, S. Y. (2019). Algorithmic aspects of homotopy theory and embeddability.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6681
chicago: Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.”
Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.
ieee: S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,”
Institute of Science and Technology Austria, 2019.
ista: Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability.
Institute of Science and Technology Austria.
mla: Zhechev, Stephan Y. Algorithmic Aspects of Homotopy Theory and Embeddability.
Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6681.
short: S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute
of Science and Technology Austria, 2019.
date_created: 2019-07-26T11:14:34Z
date_published: 2019-08-08T00:00:00Z
date_updated: 2023-09-07T13:10:36Z
day: '08'
ddc:
- '514'
degree_awarded: PhD
department:
- _id: UlWa
doi: 10.15479/AT:ISTA:6681
file:
- access_level: open_access
checksum: 3231e7cbfca3b5687366f84f0a57a0c0
content_type: application/pdf
creator: szhechev
date_created: 2019-08-07T13:02:50Z
date_updated: 2020-07-14T12:47:37Z
file_id: '6771'
file_name: Stephan_Zhechev_thesis.pdf
file_size: 1464227
relation: main_file
- access_level: closed
checksum: 85d65eb27b4377a9e332ee37a70f08b6
content_type: application/octet-stream
creator: szhechev
date_created: 2019-08-07T13:03:22Z
date_updated: 2020-07-14T12:47:37Z
file_id: '6772'
file_name: Stephan_Zhechev_thesis.tex
file_size: 303988
relation: source_file
- access_level: closed
checksum: 86b374d264ca2dd53e712728e253ee75
content_type: application/zip
creator: szhechev
date_created: 2019-08-07T13:03:34Z
date_updated: 2020-07-14T12:47:37Z
file_id: '6773'
file_name: supplementary_material.zip
file_size: 1087004
relation: supplementary_material
file_date_updated: 2020-07-14T12:47:37Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '104'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '6774'
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: Algorithmic aspects of homotopy theory and embeddability
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '6982'
abstract:
- lang: eng
text: "We present an efficient algorithm for a problem in the interface between
clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold
M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint
Jordan arcs between the corresponding vertices. In applications in clustering,
cartography, and visualization, nearby vertices and edges are often bundled to
the same point or overlapping arcs due to data compression or low resolution.
This raises the computational problem of deciding whether a given map ϕ : G →
M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed
into an embedding ψ ϵ : G → M with ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ > 0, where ‖.‖
is the unform norm.\r\nA polynomial-time algorithm for recognizing weak embeddings
has recently been found by Fulek and Kynčl. It reduces the problem to solving
a system of linear equations over Z2. It runs in O(n2ω)≤ O(n4.75) time, where
ω ∈ [2,2.373) is the matrix multiplication exponent and n is the number of vertices
and edges of G. We improve the running time to O(n log n). Our algorithm is also
conceptually simpler: We perform a sequence of local operations that gradually
“untangles” the image ϕ(G) into an embedding ψ(G) or reports that ϕ is not a weak
embedding. It combines local constraints on the orientation of subgraphs directly,
thereby eliminating the need for solving large systems of linear equations.\r\n"
article_number: '50'
article_type: original
arxiv: 1
author:
- first_name: Hugo
full_name: Akitaya, Hugo
last_name: Akitaya
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Csaba
full_name: Tóth, Csaba
last_name: Tóth
citation:
ama: Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. ACM Transactions
on Algorithms. 2019;15(4). doi:10.1145/3344549
apa: Akitaya, H., Fulek, R., & Tóth, C. (2019). Recognizing weak embeddings
of graphs. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3344549
chicago: Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings
of Graphs.” ACM Transactions on Algorithms. ACM, 2019. https://doi.org/10.1145/3344549.
ieee: H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,”
ACM Transactions on Algorithms, vol. 15, no. 4. ACM, 2019.
ista: Akitaya H, Fulek R, Tóth C. 2019. Recognizing weak embeddings of graphs. ACM
Transactions on Algorithms. 15(4), 50.
mla: Akitaya, Hugo, et al. “Recognizing Weak Embeddings of Graphs.” ACM Transactions
on Algorithms, vol. 15, no. 4, 50, ACM, 2019, doi:10.1145/3344549.
short: H. Akitaya, R. Fulek, C. Tóth, ACM Transactions on Algorithms 15 (2019).
date_created: 2019-11-04T15:45:17Z
date_published: 2019-10-01T00:00:00Z
date_updated: 2023-09-15T12:19:31Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3344549
external_id:
arxiv:
- '1709.09209'
intvolume: ' 15'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1709.09209
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: ACM Transactions on Algorithms
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '309'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Recognizing weak embeddings of graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2019'
...
---
_id: '7034'
abstract:
- lang: eng
text: We find a graph of genus 5 and its drawing on the orientable surface of genus
4 with every pair of independent edges crossing an even number of times. This
shows that the strong Hanani–Tutte theorem cannot be extended to the orientable
surface of genus 4. As a base step in the construction we use a counterexample
to an extension of the unified Hanani–Tutte theorem on the torus.
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: Jan
full_name: Kynčl, Jan
last_name: Kynčl
citation:
ama: Fulek R, Kynčl J. Counterexample to an extension of the Hanani-Tutte theorem
on the surface of genus 4. Combinatorica. 2019;39(6):1267-1279. doi:10.1007/s00493-019-3905-7
apa: Fulek, R., & Kynčl, J. (2019). Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-019-3905-7
chicago: Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the
Hanani-Tutte Theorem on the Surface of Genus 4.” Combinatorica. Springer
Nature, 2019. https://doi.org/10.1007/s00493-019-3905-7.
ieee: R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4,” Combinatorica, vol. 39, no. 6. Springer
Nature, pp. 1267–1279, 2019.
ista: Fulek R, Kynčl J. 2019. Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4. Combinatorica. 39(6), 1267–1279.
mla: Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte
Theorem on the Surface of Genus 4.” Combinatorica, vol. 39, no. 6, Springer
Nature, 2019, pp. 1267–79, doi:10.1007/s00493-019-3905-7.
short: R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.
date_created: 2019-11-18T14:29:50Z
date_published: 2019-10-29T00:00:00Z
date_updated: 2023-08-30T07:26:25Z
day: '29'
department:
- _id: UlWa
doi: 10.1007/s00493-019-3905-7
ec_funded: 1
external_id:
arxiv:
- '1709.00508'
isi:
- '000493267200003'
intvolume: ' 39'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1709.00508
month: '10'
oa: 1
oa_version: Preprint
page: 1267-1279
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counterexample to an extension of the Hanani-Tutte theorem on the surface of
genus 4
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 39
year: '2019'
...
---
_id: '7093'
abstract:
- lang: eng
text: "In graph theory, as well as in 3-manifold topology, there exist several width-type
parameters to describe how \"simple\" or \"thin\" a given graph or 3-manifold
is. These parameters, such as pathwidth or treewidth for graphs, or the concept
of thin position for 3-manifolds, play an important role when studying algorithmic
problems; in particular, there is a variety of problems in computational 3-manifold
topology - some of them known to be computationally hard in general - that become
solvable in polynomial time as soon as the dual graph of the input triangulation
has bounded treewidth.\r\nIn view of these algorithmic results, it is natural
to ask whether every 3-manifold admits a triangulation of bounded treewidth. We
show that this is not the case, i.e., that there exists an infinite family of
closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth
(the latter implies the former, but we present two separate proofs).\r\nWe derive
these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann,
Schultens and Saito by exhibiting explicit connections between the topology of
a 3-manifold M on the one hand and width-type parameters of the dual graphs of
triangulations of M on the other hand, answering a question that had been raised
repeatedly by researchers in computational 3-manifold topology. In particular,
we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has
a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M
is at most 18(k+1) (resp. 4(3k+1))."
article_processing_charge: No
article_type: original
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
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds.
Journal of Computational Geometry. 2019;10(2):70–98. doi:10.20382/JOGC.V10I2A5
apa: Huszár, K., Spreer, J., & Wagner, U. (2019). On the treewidth of triangulated
3-manifolds. Journal of Computational Geometry. Computational Geometry
Laborartoy. https://doi.org/10.20382/JOGC.V10I2A5
chicago: Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of
Triangulated 3-Manifolds.” Journal of Computational Geometry. Computational
Geometry Laborartoy, 2019. https://doi.org/10.20382/JOGC.V10I2A5.
ieee: K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,”
Journal of Computational Geometry, vol. 10, no. 2. Computational Geometry
Laborartoy, pp. 70–98, 2019.
ista: Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds.
Journal of Computational Geometry. 10(2), 70–98.
mla: Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” Journal
of Computational Geometry, vol. 10, no. 2, Computational Geometry Laborartoy,
2019, pp. 70–98, doi:10.20382/JOGC.V10I2A5.
short: K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019)
70–98.
date_created: 2019-11-23T12:14:09Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2023-09-07T13:18:26Z
day: '01'
ddc:
- '514'
department:
- _id: UlWa
doi: 10.20382/JOGC.V10I2A5
external_id:
arxiv:
- '1712.00434'
file:
- access_level: open_access
checksum: c872d590d38d538404782bca20c4c3f5
content_type: application/pdf
creator: khuszar
date_created: 2019-11-23T12:35:16Z
date_updated: 2020-07-14T12:47:49Z
file_id: '7094'
file_name: 479-1917-1-PB.pdf
file_size: 857590
relation: main_file
file_date_updated: 2020-07-14T12:47:49Z
has_accepted_license: '1'
intvolume: ' 10'
issue: '2'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 70–98
publication: Journal of Computational Geometry
publication_identifier:
issn:
- 1920-180X
publication_status: published
publisher: Computational Geometry Laborartoy
quality_controlled: '1'
related_material:
record:
- id: '285'
relation: earlier_version
status: public
- id: '8032'
relation: part_of_dissertation
status: public
status: public
title: On the treewidth of triangulated 3-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: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 10
year: '2019'
...