---
_id: '7666'
abstract:
- lang: eng
text: Generalizing the decomposition of a connected planar graph into a tree and
a dual tree, we prove a combinatorial analog of the classic Helmholtz–Hodge decomposition
of a smooth vector field. Specifically, we show that for every polyhedral complex,
K, and every dimension, p, there is a partition of the set of p-cells into a maximal
p-tree, a maximal p-cotree, and a collection of p-cells whose cardinality is the
p-th reduced Betti number of K. Given an ordering of the p-cells, this tri-partition
is unique, and it can be computed by a matrix reduction algorithm that also constructs
canonical bases of cycle and boundary groups.
acknowledgement: This project has received funding from the European Research Council
under the European Union’s Horizon 2020 research and innovation programme (Grant
Agreement No. 78818 Alpha). It is also partially supported by the DFG Collaborative
Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, through Grant
No. I02979-N35 of the Austrian Science Fund (FWF).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Katharina
full_name: Ölsböck, Katharina
id: 4D4AA390-F248-11E8-B48F-1D18A9856A87
last_name: Ölsböck
orcid: 0000-0002-4672-8297
citation:
ama: Edelsbrunner H, Ölsböck K. Tri-partitions and bases of an ordered complex.
Discrete and Computational Geometry. 2020;64:759-775. doi:10.1007/s00454-020-00188-x
apa: Edelsbrunner, H., & Ölsböck, K. (2020). Tri-partitions and bases of an
ordered complex. Discrete and Computational Geometry. Springer Nature.
https://doi.org/10.1007/s00454-020-00188-x
chicago: Edelsbrunner, Herbert, and Katharina Ölsböck. “Tri-Partitions and Bases
of an Ordered Complex.” Discrete and Computational Geometry. Springer Nature,
2020. https://doi.org/10.1007/s00454-020-00188-x.
ieee: H. Edelsbrunner and K. Ölsböck, “Tri-partitions and bases of an ordered complex,”
Discrete and Computational Geometry, vol. 64. Springer Nature, pp. 759–775,
2020.
ista: Edelsbrunner H, Ölsböck K. 2020. Tri-partitions and bases of an ordered complex.
Discrete and Computational Geometry. 64, 759–775.
mla: Edelsbrunner, Herbert, and Katharina Ölsböck. “Tri-Partitions and Bases of
an Ordered Complex.” Discrete and Computational Geometry, vol. 64, Springer
Nature, 2020, pp. 759–75, doi:10.1007/s00454-020-00188-x.
short: H. Edelsbrunner, K. Ölsböck, Discrete and Computational Geometry 64 (2020)
759–775.
date_created: 2020-04-19T22:00:56Z
date_published: 2020-03-20T00:00:00Z
date_updated: 2023-08-21T06:13:48Z
day: '20'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00188-x
ec_funded: 1
external_id:
isi:
- '000520918800001'
file:
- access_level: open_access
checksum: f8cc96e497f00c38340b5dafe0cb91d7
content_type: application/pdf
creator: dernst
date_created: 2020-11-20T13:22:21Z
date_updated: 2020-11-20T13:22:21Z
file_id: '8786'
file_name: 2020_DiscreteCompGeo_Edelsbrunner.pdf
file_size: 701673
relation: main_file
success: 1
file_date_updated: 2020-11-20T13:22:21Z
has_accepted_license: '1'
intvolume: ' 64'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 759-775
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
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: Tri-partitions and bases of an ordered complex
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...
---
_id: '7960'
abstract:
- lang: eng
text: Let A={A1,…,An} be a family of sets in the plane. For 0≤i2b be integers. We prove that if each k-wise or (k+1)-wise intersection
of sets from A has at most b path-connected components, which all are open, then
fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k.
These results also extend to two-dimensional compact surfaces.
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
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. Discrete and
Computational Geometry. 2020;64:304-323. doi:10.1007/s00454-020-00205-z
apa: Kalai, G., & Patakova, Z. (2020). Intersection patterns of planar sets.
Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00205-z
chicago: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.”
Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00205-z.
ieee: G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” Discrete
and Computational Geometry, 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.” Discrete
and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 304–23, doi:10.1007/s00454-020-00205-z.
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: '7962'
abstract:
- lang: eng
text: 'A string graph is the intersection graph of a family of continuous arcs in
the plane. The intersection graph of a family of plane convex sets is a string
graph, but not all string graphs can be obtained in this way. We prove the following
structure theorem conjectured by Janson and Uzzell: The vertex set of almost all
string graphs on n vertices can be partitioned into five cliques such that some
pair of them is not connected by any edge (n→∞). We also show that every graph
with the above property is an intersection graph of plane convex sets. As a corollary,
we obtain that almost all string graphs on n vertices are intersection graphs
of plane convex sets.'
article_processing_charge: No
article_type: original
author:
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: Bruce
full_name: Reed, Bruce
last_name: Reed
- first_name: Yelena
full_name: Yuditsky, Yelena
last_name: Yuditsky
citation:
ama: Pach J, Reed B, Yuditsky Y. Almost all string graphs are intersection graphs
of plane convex sets. Discrete and Computational Geometry. 2020;63(4):888-917.
doi:10.1007/s00454-020-00213-z
apa: Pach, J., Reed, B., & Yuditsky, Y. (2020). Almost all string graphs are
intersection graphs of plane convex sets. Discrete and Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-020-00213-z
chicago: Pach, János, Bruce Reed, and Yelena Yuditsky. “Almost All String Graphs
Are Intersection Graphs of Plane Convex Sets.” Discrete and Computational Geometry.
Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00213-z.
ieee: J. Pach, B. Reed, and Y. Yuditsky, “Almost all string graphs are intersection
graphs of plane convex sets,” Discrete and Computational Geometry, vol.
63, no. 4. Springer Nature, pp. 888–917, 2020.
ista: Pach J, Reed B, Yuditsky Y. 2020. Almost all string graphs are intersection
graphs of plane convex sets. Discrete and Computational Geometry. 63(4), 888–917.
mla: Pach, János, et al. “Almost All String Graphs Are Intersection Graphs of Plane
Convex Sets.” Discrete and Computational Geometry, vol. 63, no. 4, Springer
Nature, 2020, pp. 888–917, doi:10.1007/s00454-020-00213-z.
short: J. Pach, B. Reed, Y. Yuditsky, Discrete and Computational Geometry 63 (2020)
888–917.
date_created: 2020-06-14T22:00:51Z
date_published: 2020-06-05T00:00:00Z
date_updated: 2023-08-21T08:49:18Z
day: '05'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00213-z
external_id:
arxiv:
- '1803.06710'
isi:
- '000538229000001'
intvolume: ' 63'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.06710
month: '06'
oa: 1
oa_version: Preprint
page: 888-917
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
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: Almost all string graphs are intersection graphs of plane convex sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 63
year: '2020'
...
---
_id: '8323'
article_processing_charge: No
article_type: letter_note
author:
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
citation:
ama: Pach J. A farewell to Ricky Pollack. Discrete and Computational Geometry.
2020;64:571-574. doi:10.1007/s00454-020-00237-5
apa: Pach, J. (2020). A farewell to Ricky Pollack. Discrete and Computational
Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00237-5
chicago: Pach, János. “A Farewell to Ricky Pollack.” Discrete and Computational
Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00237-5.
ieee: J. Pach, “A farewell to Ricky Pollack,” Discrete and Computational Geometry,
vol. 64. Springer Nature, pp. 571–574, 2020.
ista: Pach J. 2020. A farewell to Ricky Pollack. Discrete and Computational Geometry.
64, 571–574.
mla: Pach, János. “A Farewell to Ricky Pollack.” Discrete and Computational Geometry,
vol. 64, Springer Nature, 2020, pp. 571–74, doi:10.1007/s00454-020-00237-5.
short: J. Pach, Discrete and Computational Geometry 64 (2020) 571–574.
date_created: 2020-08-30T22:01:12Z
date_published: 2020-10-01T00:00:00Z
date_updated: 2023-08-22T09:05:04Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00454-020-00237-5
external_id:
isi:
- '000561483500001'
intvolume: ' 64'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00454-020-00237-5
month: '10'
oa: 1
oa_version: None
page: 571-574
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- '14320444'
issn:
- '01795376'
publication_status: published
publisher: Springer Nature
scopus_import: '1'
status: public
title: A farewell to Ricky Pollack
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...
---
_id: '5678'
abstract:
- lang: eng
text: "The order-k Voronoi tessellation of a locally finite set \U0001D44B⊆ℝ\U0001D45B
decomposes ℝ\U0001D45B into convex domains whose points have the same k nearest
neighbors in X. Assuming X is a stationary Poisson point process, we give explicit
formulas for the expected number and total area of faces of a given dimension
per unit volume of space. We also develop a relaxed version of discrete Morse
theory and generalize by counting only faces, for which the k nearest points in
X are within a given distance threshold."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Anton
full_name: Nikitenko, Anton
id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87
last_name: Nikitenko
orcid: 0000-0002-0659-3201
citation:
ama: Edelsbrunner H, Nikitenko A. Poisson–Delaunay Mosaics of Order k. Discrete
and Computational Geometry. 2019;62(4):865–878. doi:10.1007/s00454-018-0049-2
apa: Edelsbrunner, H., & Nikitenko, A. (2019). Poisson–Delaunay Mosaics of Order
k. Discrete and Computational Geometry. Springer. https://doi.org/10.1007/s00454-018-0049-2
chicago: Edelsbrunner, Herbert, and Anton Nikitenko. “Poisson–Delaunay Mosaics of
Order K.” Discrete and Computational Geometry. Springer, 2019. https://doi.org/10.1007/s00454-018-0049-2.
ieee: H. Edelsbrunner and A. Nikitenko, “Poisson–Delaunay Mosaics of Order k,” Discrete
and Computational Geometry, vol. 62, no. 4. Springer, pp. 865–878, 2019.
ista: Edelsbrunner H, Nikitenko A. 2019. Poisson–Delaunay Mosaics of Order k. Discrete
and Computational Geometry. 62(4), 865–878.
mla: Edelsbrunner, Herbert, and Anton Nikitenko. “Poisson–Delaunay Mosaics of Order
K.” Discrete and Computational Geometry, vol. 62, no. 4, Springer, 2019,
pp. 865–878, doi:10.1007/s00454-018-0049-2.
short: H. Edelsbrunner, A. Nikitenko, Discrete and Computational Geometry 62 (2019)
865–878.
date_created: 2018-12-16T22:59:20Z
date_published: 2019-12-01T00:00:00Z
date_updated: 2023-09-07T12:07:12Z
day: '01'
ddc:
- '516'
department:
- _id: HeEd
doi: 10.1007/s00454-018-0049-2
ec_funded: 1
external_id:
arxiv:
- '1709.09380'
isi:
- '000494042900008'
file:
- access_level: open_access
checksum: f9d00e166efaccb5a76bbcbb4dcea3b4
content_type: application/pdf
creator: dernst
date_created: 2019-02-06T10:10:46Z
date_updated: 2020-07-14T12:47:10Z
file_id: '5932'
file_name: 2018_DiscreteCompGeometry_Edelsbrunner.pdf
file_size: 599339
relation: main_file
file_date_updated: 2020-07-14T12:47:10Z
has_accepted_license: '1'
intvolume: ' 62'
isi: 1
issue: '4'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 865–878
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- '14320444'
issn:
- '01795376'
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
record:
- id: '6287'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Poisson–Delaunay Mosaics of Order k
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 62
year: '2019'
...
---
_id: '1064'
abstract:
- lang: eng
text: 'In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by
P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it
is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot
be separated into two subfamilies by a straight line disjoint from the disks.
In this note we show that essentially the same idea may work for different analogues
and generalizations of their result. In particular, we prove the following: Given
a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety
coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate
of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane
disjoint from the homothets.'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Alexey
full_name: Balitskiy, Alexey
last_name: Balitskiy
- first_name: Mikhail
full_name: Grigorev, Mikhail
last_name: Grigorev
citation:
ama: Akopyan A, Balitskiy A, Grigorev M. On the circle covering theorem by A.W.
Goodman and R.E. Goodman. Discrete & Computational Geometry. 2018;59(4):1001-1009.
doi:10.1007/s00454-017-9883-x
apa: Akopyan, A., Balitskiy, A., & Grigorev, M. (2018). On the circle covering
theorem by A.W. Goodman and R.E. Goodman. Discrete & Computational Geometry.
Springer. https://doi.org/10.1007/s00454-017-9883-x
chicago: Akopyan, Arseniy, Alexey Balitskiy, and Mikhail Grigorev. “On the Circle
Covering Theorem by A.W. Goodman and R.E. Goodman.” Discrete & Computational
Geometry. Springer, 2018. https://doi.org/10.1007/s00454-017-9883-x.
ieee: A. Akopyan, A. Balitskiy, and M. Grigorev, “On the circle covering theorem
by A.W. Goodman and R.E. Goodman,” Discrete & Computational Geometry,
vol. 59, no. 4. Springer, pp. 1001–1009, 2018.
ista: Akopyan A, Balitskiy A, Grigorev M. 2018. On the circle covering theorem by
A.W. Goodman and R.E. Goodman. Discrete & Computational Geometry. 59(4), 1001–1009.
mla: Akopyan, Arseniy, et al. “On the Circle Covering Theorem by A.W. Goodman and
R.E. Goodman.” Discrete & Computational Geometry, vol. 59, no. 4, Springer,
2018, pp. 1001–09, doi:10.1007/s00454-017-9883-x.
short: A. Akopyan, A. Balitskiy, M. Grigorev, Discrete & Computational Geometry
59 (2018) 1001–1009.
date_created: 2018-12-11T11:49:57Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2023-09-20T12:08:51Z
day: '01'
ddc:
- '516'
- '000'
department:
- _id: HeEd
doi: 10.1007/s00454-017-9883-x
ec_funded: 1
external_id:
isi:
- '000432205500011'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T09:27:36Z
date_updated: 2019-01-18T09:27:36Z
file_id: '5844'
file_name: 2018_DiscreteComp_Akopyan.pdf
file_size: 482518
relation: main_file
success: 1
file_date_updated: 2019-01-18T09:27:36Z
has_accepted_license: '1'
intvolume: ' 59'
isi: 1
issue: '4'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1001-1009
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- '14320444'
issn:
- '01795376'
publication_status: published
publisher: Springer
publist_id: '6324'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the circle covering theorem by A.W. Goodman and R.E. Goodman
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: 59
year: '2018'
...
---
_id: '534'
abstract:
- lang: eng
text: We investigate the complexity of finding an embedded non-orientable surface
of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural
question in low-dimensional topology, and as a first non-trivial instance of embeddability
of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding
to the relatively few hardness results that are currently known in 3-manifold
topology. In addition, we show that the problem lies in NP when the Euler genus
g is odd, and we give an explicit algorithm in this case.
article_processing_charge: No
article_type: original
author:
- first_name: Benjamin
full_name: Burton, Benjamin
last_name: Burton
- first_name: Arnaud N
full_name: De Mesmay, Arnaud N
id: 3DB2F25C-F248-11E8-B48F-1D18A9856A87
last_name: De Mesmay
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-Manifolds.
Discrete & Computational Geometry. 2017;58(4):871-888. doi:10.1007/s00454-017-9900-0
apa: Burton, B., de Mesmay, A. N., & Wagner, U. (2017). Finding non-orientable
surfaces in 3-Manifolds. Discrete & Computational Geometry. Springer.
https://doi.org/10.1007/s00454-017-9900-0
chicago: Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable
Surfaces in 3-Manifolds.” Discrete & Computational Geometry. Springer,
2017. https://doi.org/10.1007/s00454-017-9900-0.
ieee: B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces
in 3-Manifolds,” Discrete & Computational Geometry, vol. 58, no. 4.
Springer, pp. 871–888, 2017.
ista: Burton B, de Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in
3-Manifolds. Discrete & Computational Geometry. 58(4), 871–888.
mla: Burton, Benjamin, et al. “Finding Non-Orientable Surfaces in 3-Manifolds.”
Discrete & Computational Geometry, vol. 58, no. 4, Springer, 2017,
pp. 871–88, doi:10.1007/s00454-017-9900-0.
short: B. Burton, A.N. de Mesmay, U. Wagner, Discrete & Computational Geometry
58 (2017) 871–888.
date_created: 2018-12-11T11:47:01Z
date_published: 2017-06-09T00:00:00Z
date_updated: 2023-02-21T17:01:34Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/s00454-017-9900-0
external_id:
arxiv:
- '1602.07907'
intvolume: ' 58'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.07907
month: '06'
oa: 1
oa_version: Preprint
page: 871 - 888
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- '01795376'
publication_status: published
publisher: Springer
publist_id: '7283'
quality_controlled: '1'
related_material:
record:
- id: '1379'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Finding non-orientable surfaces in 3-Manifolds
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 58
year: '2017'
...
---
_id: '1073'
abstract:
- lang: eng
text: Let X and Y be finite simplicial sets (e.g. finite simplicial complexes),
both equipped with a free simplicial action of a finite group G. Assuming that
Y is d-connected and dimX≤2d, for some d≥1, we provide an algorithm that computes
the set of all equivariant homotopy classes of equivariant continuous maps |X|→|Y|;
the existence of such a map can be decided even for dimX≤2d+1. This yields the
first algorithm for deciding topological embeddability of a k-dimensional finite
simplicial complex into Rn under the condition k≤23n−1. More generally, we present
an algorithm that, given a lifting-extension problem satisfying an appropriate
stability assumption, computes the set of all homotopy classes of solutions. This
result is new even in the non-equivariant situation.
article_processing_charge: No
author:
- first_name: Martin
full_name: Čadek, Martin
last_name: Čadek
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
- first_name: Lukáš
full_name: Vokřínek, Lukáš
last_name: Vokřínek
citation:
ama: Čadek M, Krcál M, Vokřínek L. Algorithmic solvability of the lifting extension
problem. Discrete & Computational Geometry. 2017;54(4):915-965. doi:10.1007/s00454-016-9855-6
apa: Čadek, M., Krcál, M., & Vokřínek, L. (2017). Algorithmic solvability of
the lifting extension problem. Discrete & Computational Geometry. Springer.
https://doi.org/10.1007/s00454-016-9855-6
chicago: Čadek, Martin, Marek Krcál, and Lukáš Vokřínek. “Algorithmic Solvability
of the Lifting Extension Problem.” Discrete & Computational Geometry.
Springer, 2017. https://doi.org/10.1007/s00454-016-9855-6.
ieee: M. Čadek, M. Krcál, and L. Vokřínek, “Algorithmic solvability of the lifting
extension problem,” Discrete & Computational Geometry, vol. 54, no.
4. Springer, pp. 915–965, 2017.
ista: Čadek M, Krcál M, Vokřínek L. 2017. Algorithmic solvability of the lifting
extension problem. Discrete & Computational Geometry. 54(4), 915–965.
mla: Čadek, Martin, et al. “Algorithmic Solvability of the Lifting Extension Problem.”
Discrete & Computational Geometry, vol. 54, no. 4, Springer, 2017,
pp. 915–65, doi:10.1007/s00454-016-9855-6.
short: M. Čadek, M. Krcál, L. Vokřínek, Discrete & Computational Geometry 54
(2017) 915–965.
date_created: 2018-12-11T11:50:00Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T12:01:28Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-016-9855-6
external_id:
isi:
- '000400072700008'
intvolume: ' 54'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1307.6444
month: '06'
oa: 1
oa_version: Submitted Version
page: 915 - 965
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- '01795376'
publication_status: published
publisher: Springer
publist_id: '6309'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithmic solvability of the lifting extension problem
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 54
year: '2017'
...