---
OA_place: publisher
_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.
corr_author: '1'
date_created: 2019-07-26T11:14:34Z
date_published: 2019-08-08T00:00:00Z
date_updated: 2026-04-16T12:20:40Z
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
license: https://creativecommons.org/licenses/by/4.0/
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
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: 2025-04-14T13:52:37Z
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: 2025-04-14T13:52:37Z
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: 2026-04-08T07:21:27Z
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
scopus_import: '1'
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'
...
---
_id: '7108'
abstract:
- lang: eng
text: We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial
complex is shellable is NP-hard, hence NP-complete. This resolves a question raised,
e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d
≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable
is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible
pure d-dimensional complexes. Another simple corollary of our result is that it
is NP-hard to decide whether a given poset is CL-shellable.
article_number: '21'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xavier
full_name: Goaoc, Xavier
last_name: Goaoc
- first_name: Pavel
full_name: Patak, Pavel
id: B593B804-1035-11EA-B4F1-947645A5BB83
last_name: Patak
- 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
last_name: Tancer
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete.
Journal of the ACM. 2019;66(3). doi:10.1145/3314024
apa: Goaoc, X., Patak, P., Patakova, Z., Tancer, M., & Wagner, U. (2019). Shellability
is NP-complete. Journal of the ACM. ACM. https://doi.org/10.1145/3314024
chicago: Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner.
“Shellability Is NP-Complete.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3314024.
ieee: X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is
NP-complete,” Journal of the ACM, vol. 66, no. 3. ACM, 2019.
ista: Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete.
Journal of the ACM. 66(3), 21.
mla: Goaoc, Xavier, et al. “Shellability Is NP-Complete.” Journal of the ACM,
vol. 66, no. 3, 21, ACM, 2019, doi:10.1145/3314024.
short: X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM
66 (2019).
date_created: 2019-11-26T10:13:59Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2025-06-04T07:49:03Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3314024
external_id:
arxiv:
- '1711.08436'
isi:
- '000495406300007'
intvolume: ' 66'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1711.08436
month: '06'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_identifier:
issn:
- 0004-5411
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '184'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Shellability is NP-complete
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2019'
...
---
_id: '7230'
abstract:
- lang: eng
text: Simple drawings of graphs are those in which each pair of edges share at most
one point, either a common endpoint or a proper crossing. In this paper we study
the problem of extending a simple drawing D(G) of a graph G by inserting a set
of edges from the complement of G into D(G) such that the result is a simple drawing.
In the context of rectilinear drawings, the problem is trivial. For pseudolinear
drawings, the existence of such an extension follows from Levi’s enlargement lemma.
In contrast, we prove that deciding if a given set of edges can be inserted into
a simple drawing is NP-complete. Moreover, we show that the maximization version
of the problem is APX-hard. We also present a polynomial-time algorithm for deciding
whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for
the graph G.
alternative_title:
- LNCS
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: Martin
full_name: Derka, Martin
last_name: Derka
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
citation:
ama: 'Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: 27th
International Symposium on Graph Drawing and Network Visualization. Vol 11904.
Springer Nature; 2019:230-243. doi:10.1007/978-3-030-35802-0_18'
apa: 'Arroyo Guevara, A. M., Derka, M., & Parada, I. (2019). Extending simple
drawings. In 27th International Symposium on Graph Drawing and Network Visualization
(Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. https://doi.org/10.1007/978-3-030-35802-0_18'
chicago: Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple
Drawings.” In 27th International Symposium on Graph Drawing and Network Visualization,
11904:230–43. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-35802-0_18.
ieee: A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,”
in 27th International Symposium on Graph Drawing and Network Visualization,
Prague, Czech Republic, 2019, vol. 11904, pp. 230–243.
ista: 'Arroyo Guevara AM, Derka M, Parada I. 2019. Extending simple drawings. 27th
International Symposium on Graph Drawing and Network Visualization. GD: Graph
Drawing and Network Visualization, LNCS, vol. 11904, 230–243.'
mla: Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” 27th International
Symposium on Graph Drawing and Network Visualization, vol. 11904, Springer
Nature, 2019, pp. 230–43, doi:10.1007/978-3-030-35802-0_18.
short: A.M. Arroyo Guevara, M. Derka, I. Parada, in:, 27th International Symposium
on Graph Drawing and Network Visualization, Springer Nature, 2019, pp. 230–243.
conference:
end_date: 2019-09-20
location: Prague, Czech Republic
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2019-09-17
date_created: 2020-01-05T23:00:47Z
date_published: 2019-11-28T00:00:00Z
date_updated: 2025-04-14T07:44:07Z
day: '28'
department:
- _id: UlWa
doi: 10.1007/978-3-030-35802-0_18
ec_funded: 1
external_id:
arxiv:
- '1908.08129'
isi:
- '000612918800018'
intvolume: ' 11904'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1908.08129
month: '11'
oa: 1
oa_version: Preprint
page: 230-243
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 27th International Symposium on Graph Drawing and Network Visualization
publication_identifier:
eissn:
- 1611-3349
isbn:
- 978-3-0303-5801-3
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending simple drawings
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11904
year: '2019'
...
---
_id: '7401'
abstract:
- lang: eng
text: 'The genus g(G) of a graph G is the minimum g such that G has an embedding
on the orientable surface M_g of genus g. A drawing of a graph on a surface is
independently even if every pair of nonadjacent edges in the drawing crosses an
even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum
g such that G has an independently even drawing on M_g. By a result of Battle,
Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected
blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph
is additive over 2-connected blocks as well, and asked whether this result can
be extended to so-called 2-amalgamations, as an analogue of results by Decker,
Glover, Huneke, and Stahl for the genus. We give the following partial answer.
If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has
k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1.
For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n).
Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus
of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem
that might be of independent interest. '
alternative_title:
- LIPIcs
article_number: '39'
article_processing_charge: No
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: Kyncl, Jan
last_name: Kyncl
citation:
ama: 'Fulek R, Kyncl J. Z_2-Genus of graphs and minimum rank of partial symmetric
matrices. In: 35th International Symposium on Computational Geometry (SoCG
2019). Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.SOCG.2019.39'
apa: 'Fulek, R., & Kyncl, J. (2019). Z_2-Genus of graphs and minimum rank of
partial symmetric matrices. In 35th International Symposium on Computational
Geometry (SoCG 2019) (Vol. 129). Portland, OR, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.39'
chicago: Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of
Partial Symmetric Matrices.” In 35th International Symposium on Computational
Geometry (SoCG 2019), Vol. 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019. https://doi.org/10.4230/LIPICS.SOCG.2019.39.
ieee: R. Fulek and J. Kyncl, “Z_2-Genus of graphs and minimum rank of partial symmetric
matrices,” in 35th International Symposium on Computational Geometry (SoCG
2019), Portland, OR, United States, 2019, vol. 129.
ista: 'Fulek R, Kyncl J. 2019. Z_2-Genus of graphs and minimum rank of partial symmetric
matrices. 35th International Symposium on Computational Geometry (SoCG 2019).
SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 39.'
mla: Fulek, Radoslav, and Jan Kyncl. “Z_2-Genus of Graphs and Minimum Rank of Partial
Symmetric Matrices.” 35th International Symposium on Computational Geometry
(SoCG 2019), vol. 129, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019, doi:10.4230/LIPICS.SOCG.2019.39.
short: R. Fulek, J. Kyncl, in:, 35th International Symposium on Computational Geometry
(SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
conference:
end_date: 2019-06-21
location: Portland, OR, United States
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2019-06-18
corr_author: '1'
date_created: 2020-01-29T16:17:05Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2024-10-09T20:59:14Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.39
external_id:
arxiv:
- '1903.08637'
file:
- access_level: open_access
checksum: aac37b09118cc0ab58cf77129e691f8c
content_type: application/pdf
creator: dernst
date_created: 2020-02-04T09:14:31Z
date_updated: 2020-07-14T12:47:57Z
file_id: '7445'
file_name: 2019_LIPIcs_Fulek.pdf
file_size: 628347
relation: main_file
file_date_updated: 2020-07-14T12:47:57Z
has_accepted_license: '1'
intvolume: ' 129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
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 (SoCG 2019)
publication_identifier:
isbn:
- 978-3-95977-104-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Z_2-Genus of graphs and minimum rank of partial symmetric matrices
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: '285'
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. In 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). We derive
these results from work of Agol and of Scharlemann and Thompson, 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 48(k+1) (resp. 4(3k+1)).
acknowledgement: Research of the second author was supported by the Einstein Foundation
(project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons
Visiting Professors” program).
alternative_title:
- LIPIcs
article_number: '46'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kristóf
full_name: Huszár, Kristóf
id: 33C26278-F248-11E8-B48F-1D18A9856A87
last_name: Huszár
orcid: 0000-0002-5445-5057
- first_name: Jonathan
full_name: Spreer, Jonathan
last_name: Spreer
- 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.
In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.46'
apa: 'Huszár, K., Spreer, J., & Wagner, U. (2018). On the treewidth of triangulated
3-manifolds (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry,
Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.46'
chicago: Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of
Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.46.
ieee: 'K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,”
presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary,
2018, vol. 99.'
ista: 'Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds.
SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.'
mla: Huszár, Kristóf, et al. On the Treewidth of Triangulated 3-Manifolds.
Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.46.
short: K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2018.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:37Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2025-07-10T11:52:21Z
day: '01'
ddc:
- '516'
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.46
external_id:
arxiv:
- '1712.00434'
file:
- access_level: open_access
checksum: 530d084116778135d5bffaa317479cac
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T15:32:38Z
date_updated: 2020-07-14T12:45:51Z
file_id: '5713'
file_name: 2018_LIPIcs_Huszar.pdf
file_size: 642522
relation: main_file
file_date_updated: 2020-07-14T12:45:51Z
has_accepted_license: '1'
intvolume: ' 99'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
publication_identifier:
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7614'
quality_controlled: '1'
related_material:
record:
- id: '7093'
relation: later_version
status: public
scopus_import: '1'
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 99
year: '2018'
...
---
_id: '185'
abstract:
- lang: eng
text: We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998),
and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the
setting of approximating maps of graphs on 2-dimensional surfaces by embeddings.
Our proof of this result is constructive and almost immediately implies an efficient
algorithm for testing whether a given piecewise linear map of a graph in a surface
is approximable by an embedding. More precisely, an instance of this problem consists
of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster
edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact
surface M given as the union of a set of pairwise disjoint discs corresponding
to the clusters and a set of pairwise disjoint "pipes" corresponding
to the bundles, connecting certain pairs of these discs. We are to decide whether
G can be embedded inside M so that the vertices in every cluster are drawn in
the corresponding disc, the edges in every bundle pass only through its corresponding
pipe, and every edge crosses the boundary of each disc at most once.
alternative_title:
- Leibniz International Proceedings in Information, LIPIcs
article_number: '39'
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. Hanani-Tutte for approximating maps of graphs. In: Vol 99.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.39'
apa: 'Fulek, R., & Kynčl, J. (2018). Hanani-Tutte for approximating maps of
graphs (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry,
Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.39'
chicago: Fulek, Radoslav, and Jan Kynčl. “Hanani-Tutte for Approximating Maps of
Graphs,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.39.
ieee: 'R. Fulek and J. Kynčl, “Hanani-Tutte for approximating maps of graphs,” presented
at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol.
99.'
ista: 'Fulek R, Kynčl J. 2018. Hanani-Tutte for approximating maps of graphs. SoCG:
Symposium on Computational Geometry, Leibniz International Proceedings in Information,
LIPIcs, vol. 99, 39.'
mla: Fulek, Radoslav, and Jan Kynčl. Hanani-Tutte for Approximating Maps of Graphs.
Vol. 99, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.39.
short: R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:04Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2021-01-12T06:53:36Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.39
file:
- access_level: open_access
checksum: f1b94f1a75b37c414a1f61d59fb2cd4c
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T12:33:52Z
date_updated: 2020-07-14T12:45:19Z
file_id: '5701'
file_name: 2018_LIPIcs_Fulek.pdf
file_size: 718857
relation: main_file
file_date_updated: 2020-07-14T12:45:19Z
has_accepted_license: '1'
intvolume: ' 99'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_identifier:
isbn:
- 978-3-95977-066-8
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7735'
quality_controlled: '1'
scopus_import: 1
status: public
title: Hanani-Tutte for approximating maps of graphs
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: 99
year: '2018'
...
---
_id: '186'
abstract:
- lang: eng
text: 'A drawing of a graph on a surface is independently even if every pair of
nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus
of a graph G is the minimum g such that G has an independently even drawing on
the orientable surface of genus g. An unpublished result by Robertson and Seymour
implies that for every t, every graph of sufficiently large genus contains as
a minor a projective t × t grid or one of the following so-called t-Kuratowski
graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We
show that the ℤ2-genus of graphs in these families is unbounded in t; in fact,
equal to their genus. Together, this implies that the genus of a graph is bounded
from above by a function of its ℤ2-genus, solving a problem posed by Schaefer
and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem
on orientable surfaces.'
alternative_title:
- LIPIcs
article_processing_charge: No
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. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2018:40.1-40.14. doi:10.4230/LIPIcs.SoCG.2018.40'
apa: 'Fulek, R., & Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol.
99, p. 40.1-40.14). Presented at the SoCG: Symposium on Computational Geometry,
Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.40'
chicago: Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” 99:40.1-40.14.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.40.
ieee: 'R. Fulek and J. Kynčl, “The ℤ2-Genus of Kuratowski minors,” presented at
the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99,
p. 40.1-40.14.'
ista: 'Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium
on Computational Geometry, LIPIcs, vol. 99, 40.1-40.14.'
mla: Fulek, Radoslav, and Jan Kynčl. The ℤ2-Genus of Kuratowski Minors. Vol.
99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14, doi:10.4230/LIPIcs.SoCG.2018.40.
short: R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018, p. 40.1-40.14.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:05Z
date_published: 2018-06-11T00:00:00Z
date_updated: 2025-04-14T13:52:37Z
day: '11'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.40
external_id:
arxiv:
- '1803.05085'
intvolume: ' 99'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.05085
month: '06'
oa: 1
oa_version: Submitted Version
page: 40.1 - 40.14
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7734'
quality_controlled: '1'
related_material:
record:
- id: '11593'
relation: later_version
status: public
scopus_import: '1'
status: public
title: The ℤ2-Genus of Kuratowski minors
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 99
year: '2018'
...
---
_id: '5791'
abstract:
- lang: eng
text: Due to data compression or low resolution, nearby vertices and edges of a
graph drawing may be bundled to a common node or arc. We model such a “compromised”
drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily
small ε>0 into a proper drawing (in which the vertices are distinct points, any
two edges intersect in finitely many points, and no three edges have a common
interior point) that minimizes the number of crossings. An ε-perturbation, for
every ε>0, is given by a piecewise linear map (Formula Presented), where with
||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution
for this optimization problem when G is a cycle and the map φ has no spurs (i.e.,
no two adjacent edges are mapped to overlapping arcs). We also show that the problem
becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii)
when φ may have spurs and G is a cycle or a union of disjoint paths.
alternative_title:
- LNCS
article_processing_charge: No
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: Csaba D.
full_name: Tóth, Csaba D.
last_name: Tóth
citation:
ama: 'Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282.
Springer; 2018:229-241. doi:10.1007/978-3-030-04414-5_16'
apa: 'Fulek, R., & Tóth, C. D. (2018). Crossing minimization in perturbed drawings
(Vol. 11282, pp. 229–241). Presented at the GD: Graph Drawing and Network Visualization,
Barcelona, Spain: Springer. https://doi.org/10.1007/978-3-030-04414-5_16'
chicago: Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed
Drawings,” 11282:229–41. Springer, 2018. https://doi.org/10.1007/978-3-030-04414-5_16.
ieee: 'R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented
at the GD: Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol.
11282, pp. 229–241.'
ista: 'Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. GD:
Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241.'
mla: Fulek, Radoslav, and Csaba D. Tóth. Crossing Minimization in Perturbed Drawings.
Vol. 11282, Springer, 2018, pp. 229–41, doi:10.1007/978-3-030-04414-5_16.
short: R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.
conference:
end_date: 2018-09-28
location: Barcelona, Spain
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2018-09-26
date_created: 2018-12-30T22:59:15Z
date_published: 2018-12-18T00:00:00Z
date_updated: 2025-07-10T11:53:00Z
day: '18'
department:
- _id: UlWa
doi: 10.1007/978-3-030-04414-5_16
external_id:
arxiv:
- '1808.07608'
isi:
- '000672802500016'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1808.07608
month: '12'
oa: 1
oa_version: Preprint
page: 229-241
publication_identifier:
isbn:
- '9783030044138'
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Crossing minimization in perturbed drawings
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: '11282 '
year: '2018'
...
---
_id: '5960'
abstract:
- lang: eng
text: In this paper we present a reliable method to verify the existence of loops
along the uncertain trajectory of a robot, based on proprioceptive measurements
only, within a bounded-error context. The loop closure detection is one of the
key points in simultaneous localization and mapping (SLAM) methods, especially
in homogeneous environments with difficult scenes recognitions. The proposed approach
is generic and could be coupled with conventional SLAM algorithms to reliably
reduce their computing burden, thus improving the localization and mapping processes
in the most challenging environments such as unexplored underwater extents. To
prove that a robot performed a loop whatever the uncertainties in its evolution,
we employ the notion of topological degree that originates in the field of differential
topology. We show that a verification tool based on the topological degree is
an optimal method for proving robot loops. This is demonstrated both on datasets
from real missions involving autonomous underwater vehicles and by a mathematical
discussion.
article_processing_charge: No
arxiv: 1
author:
- first_name: Simon
full_name: Rohou, Simon
last_name: Rohou
- first_name: Peter
full_name: Franek, Peter
id: 473294AE-F248-11E8-B48F-1D18A9856A87
last_name: Franek
orcid: 0000-0001-8878-8397
- first_name: Clément
full_name: Aubry, Clément
last_name: Aubry
- first_name: Luc
full_name: Jaulin, Luc
last_name: Jaulin
citation:
ama: Rohou S, Franek P, Aubry C, Jaulin L. Proving the existence of loops in robot
trajectories. The International Journal of Robotics Research. 2018;37(12):1500-1516.
doi:10.1177/0278364918808367
apa: Rohou, S., Franek, P., Aubry, C., & Jaulin, L. (2018). Proving the existence
of loops in robot trajectories. The International Journal of Robotics Research.
SAGE Publications. https://doi.org/10.1177/0278364918808367
chicago: Rohou, Simon, Peter Franek, Clément Aubry, and Luc Jaulin. “Proving the
Existence of Loops in Robot Trajectories.” The International Journal of Robotics
Research. SAGE Publications, 2018. https://doi.org/10.1177/0278364918808367.
ieee: S. Rohou, P. Franek, C. Aubry, and L. Jaulin, “Proving the existence of loops
in robot trajectories,” The International Journal of Robotics Research,
vol. 37, no. 12. SAGE Publications, pp. 1500–1516, 2018.
ista: Rohou S, Franek P, Aubry C, Jaulin L. 2018. Proving the existence of loops
in robot trajectories. The International Journal of Robotics Research. 37(12),
1500–1516.
mla: Rohou, Simon, et al. “Proving the Existence of Loops in Robot Trajectories.”
The International Journal of Robotics Research, vol. 37, no. 12, SAGE Publications,
2018, pp. 1500–16, doi:10.1177/0278364918808367.
short: S. Rohou, P. Franek, C. Aubry, L. Jaulin, The International Journal of Robotics
Research 37 (2018) 1500–1516.
date_created: 2019-02-13T09:36:20Z
date_published: 2018-10-24T00:00:00Z
date_updated: 2023-09-19T10:41:59Z
day: '24'
department:
- _id: UlWa
doi: 10.1177/0278364918808367
external_id:
arxiv:
- '1712.01341'
isi:
- '000456881100004'
intvolume: ' 37'
isi: 1
issue: '12'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1712.01341
month: '10'
oa: 1
oa_version: Preprint
page: 1500-1516
publication: The International Journal of Robotics Research
publication_identifier:
eissn:
- 1741-3176
issn:
- 0278-3649
publication_status: published
publisher: SAGE Publications
quality_controlled: '1'
scopus_import: '1'
status: public
title: Proving the existence of loops in robot trajectories
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 37
year: '2018'
...
---
_id: '6355'
abstract:
- lang: eng
text: We prove that any cyclic quadrilateral can be inscribed in any closed convex
C1-curve. The smoothness condition is not required if the quadrilateral is a
rectangle.
article_number: e7
article_processing_charge: No
arxiv: 1
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
orcid: 0000-0002-7840-5062
citation:
ama: Akopyan A, Avvakumov S. Any cyclic quadrilateral can be inscribed in any closed
convex smooth curve. Forum of Mathematics, Sigma. 2018;6. doi:10.1017/fms.2018.7
apa: Akopyan, A., & Avvakumov, S. (2018). Any cyclic quadrilateral can be inscribed
in any closed convex smooth curve. Forum of Mathematics, Sigma. Cambridge
University Press. https://doi.org/10.1017/fms.2018.7
chicago: Akopyan, Arseniy, and Sergey Avvakumov. “Any Cyclic Quadrilateral Can Be
Inscribed in Any Closed Convex Smooth Curve.” Forum of Mathematics, Sigma.
Cambridge University Press, 2018. https://doi.org/10.1017/fms.2018.7.
ieee: A. Akopyan and S. Avvakumov, “Any cyclic quadrilateral can be inscribed in
any closed convex smooth curve,” Forum of Mathematics, Sigma, vol. 6. Cambridge
University Press, 2018.
ista: Akopyan A, Avvakumov S. 2018. Any cyclic quadrilateral can be inscribed in
any closed convex smooth curve. Forum of Mathematics, Sigma. 6, e7.
mla: Akopyan, Arseniy, and Sergey Avvakumov. “Any Cyclic Quadrilateral Can Be Inscribed
in Any Closed Convex Smooth Curve.” Forum of Mathematics, Sigma, vol. 6,
e7, Cambridge University Press, 2018, doi:10.1017/fms.2018.7.
short: A. Akopyan, S. Avvakumov, Forum of Mathematics, Sigma 6 (2018).
corr_author: '1'
date_created: 2019-04-30T06:09:57Z
date_published: 2018-05-31T00:00:00Z
date_updated: 2026-04-08T07:25:54Z
day: '31'
ddc:
- '510'
department:
- _id: UlWa
- _id: HeEd
- _id: JaMa
doi: 10.1017/fms.2018.7
ec_funded: 1
external_id:
arxiv:
- '1712.10205'
isi:
- '000433915500001'
file:
- access_level: open_access
checksum: 5a71b24ba712a3eb2e46165a38fbc30a
content_type: application/pdf
creator: dernst
date_created: 2019-04-30T06:14:58Z
date_updated: 2020-07-14T12:47:28Z
file_id: '6356'
file_name: 2018_ForumMahtematics_Akopyan.pdf
file_size: 249246
relation: main_file
file_date_updated: 2020-07-14T12:47:28Z
has_accepted_license: '1'
intvolume: ' 6'
isi: 1
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 256E75B8-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '716117'
name: Optimal Transport and Stochastic Dynamics
publication: Forum of Mathematics, Sigma
publication_identifier:
issn:
- 2050-5094
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
related_material:
record:
- id: '8156'
relation: dissertation_contains
status: public
status: public
title: Any cyclic quadrilateral can be inscribed in any closed convex smooth curve
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: 6
year: '2018'
...
---
_id: '184'
abstract:
- lang: eng
text: We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial
complex is shellable is NP-hard, hence NP-complete. This resolves a question raised,
e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d
≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable
is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible
pure d-dimensional complexes.
acknowledgement: 'Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR:
38087RM) of Czech-French collaboration.'
alternative_title:
- Leibniz International Proceedings in Information, LIPIcs
author:
- first_name: Xavier
full_name: Goaoc, Xavier
last_name: Goaoc
- first_name: Pavel
full_name: Paták, Pavel
last_name: Paták
- 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: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete.
In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16.
doi:10.4230/LIPIcs.SoCG.2018.41'
apa: 'Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2018). Shellability
is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational
Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2018.41'
chicago: Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner.
“Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.41.
ieee: 'X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Shellability
is NP-complete,” presented at the SoCG: Symposium on Computational Geometry, Budapest,
Hungary, 2018, vol. 99, p. 41:1-41:16.'
ista: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2018. Shellability is NP-complete.
SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in
Information, LIPIcs, vol. 99, 41:1-41:16.'
mla: Goaoc, Xavier, et al. Shellability Is NP-Complete. Vol. 99, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:10.4230/LIPIcs.SoCG.2018.41.
short: X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16.
conference:
end_date: 2018-06-14
location: Budapest, Hungary
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2018-06-11
date_created: 2018-12-11T11:45:04Z
date_published: 2018-06-11T00:00:00Z
date_updated: 2025-06-04T07:49:02Z
day: '11'
ddc:
- '516'
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.41
file:
- access_level: open_access
checksum: d12bdd60f04a57307867704b5f930afd
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T16:35:02Z
date_updated: 2020-07-14T12:45:18Z
file_id: '5725'
file_name: 2018_LIPIcs_Goaoc.pdf
file_size: 718414
relation: main_file
file_date_updated: 2020-07-14T12:45:18Z
has_accepted_license: '1'
intvolume: ' 99'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 41:1 - 41:16
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7736'
quality_controlled: '1'
related_material:
record:
- id: '7108'
relation: later_version
status: public
scopus_import: 1
status: public
title: Shellability is NP-complete
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: 99
year: '2018'
...
---
_id: '309'
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 2manifold
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
a common node or arc, 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 k'' "k < " for every " > 0. A polynomial-time
algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl
[14], which reduces to solving a system of linear equations over Z2. It runs in
O(n2!) O(n4:75) time, where 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 than [14]: 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 generalizes a
recent technique developed for the case that G is a cycle and the embedding is
a simple polygon [1], and combines local constraints on the orientation of subgraphs
directly, thereby eliminating the need for solving large systems of linear equations.'
acknowledgement: '∗Research supported in part by the NSF awards CCF-1422311 and CCF-1423615,
and the Science Without Borders program. The second author gratefully acknowledges
support from Austrian Science Fund (FWF): M2281-N35.'
article_processing_charge: No
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. In: ACM;
2018:274-292. doi:10.1137/1.9781611975031.20'
apa: 'Akitaya, H., Fulek, R., & Tóth, C. (2018). Recognizing weak embeddings
of graphs (pp. 274–292). Presented at the SODA: Symposium on Discrete Algorithms,
New Orleans, LA, USA: ACM. https://doi.org/10.1137/1.9781611975031.20'
chicago: Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings
of Graphs,” 274–92. ACM, 2018. https://doi.org/10.1137/1.9781611975031.20.
ieee: 'H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,”
presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA,
2018, pp. 274–292.'
ista: 'Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs.
SODA: Symposium on Discrete Algorithms, 274–292.'
mla: Akitaya, Hugo, et al. Recognizing Weak Embeddings of Graphs. ACM, 2018,
pp. 274–92, doi:10.1137/1.9781611975031.20.
short: H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.
conference:
end_date: 2018-01-10
location: New Orleans, LA, USA
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2018-01-07
date_created: 2018-12-11T11:45:45Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2025-04-14T13:52:37Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/1.9781611975031.20
external_id:
arxiv:
- '1709.09209'
isi:
- '000483921200021'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1709.09209
month: '01'
oa: 1
oa_version: Preprint
page: 274 - 292
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_status: published
publisher: ACM
publist_id: '7556'
quality_controlled: '1'
related_material:
record:
- id: '6982'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Recognizing weak embeddings of graphs
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '425'
abstract:
- lang: eng
text: 'We show that the following algorithmic problem is decidable: given a 2-dimensional
simplicial complex, can it be embedded (topologically, or equivalently, piecewise
linearly) in R3? By a known reduction, it suffices to decide the embeddability
of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which
allows us to simplify X and recurse, is in proving that if X can be embedded in
S3, then there is also an embedding in which X has a short meridian, that is,
an essential curve in the boundary of X bounding a disk in S3 \ X with length
bounded by a computable function of the number of tetrahedra of X.'
article_number: '5'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- 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: Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is
decidable. Journal of the ACM. 2018;65(1). doi:10.1145/3078632
apa: Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2018). Embeddability
in the 3-Sphere is decidable. Journal of the ACM. ACM. https://doi.org/10.1145/3078632
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability
in the 3-Sphere Is Decidable.” Journal of the ACM. ACM, 2018. https://doi.org/10.1145/3078632.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the
3-Sphere is decidable,” Journal of the ACM, vol. 65, no. 1. ACM, 2018.
ista: Matoušek J, Sedgwick E, Tancer M, Wagner U. 2018. Embeddability in the 3-Sphere
is decidable. Journal of the ACM. 65(1), 5.
mla: Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” Journal
of the ACM, vol. 65, no. 1, 5, ACM, 2018, doi:10.1145/3078632.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018).
date_created: 2018-12-11T11:46:24Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2025-06-11T07:59:02Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3078632
ec_funded: 1
external_id:
arxiv:
- '1402.0815'
isi:
- '000425685900006'
intvolume: ' 65'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1402.0815
month: '01'
oa: 1
oa_version: Preprint
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '7398'
quality_controlled: '1'
related_material:
record:
- id: '2157'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Embeddability in the 3-Sphere is decidable
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 65
year: '2018'
...
---
_id: '433'
abstract:
- lang: eng
text: 'A thrackle is a graph drawn in the plane so that every pair of its edges
meet exactly once: either at a common end vertex or in a proper crossing. We prove
that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are
defined similarly, except that every pair of edges that do not share a vertex
are allowed to cross an odd number of times. It is also shown that the maximum
number of edges of a quasi-thrackle on n vertices is 3/2(n-1), and that this bound
is best possible for infinitely many values of n.'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: János
full_name: Pach, János
last_name: Pach
citation:
ama: 'Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer;
2018:160-166. doi:10.1007/978-3-319-73915-1_14'
apa: 'Fulek, R., & Pach, J. (2018). Thrackles: An improved upper bound (Vol.
10692, pp. 160–166). Presented at the GD: Graph Drawing and Network Visualization,
Boston, MA, United States: Springer. https://doi.org/10.1007/978-3-319-73915-1_14'
chicago: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,”
10692:160–66. Springer, 2018. https://doi.org/10.1007/978-3-319-73915-1_14.'
ieee: 'R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at
the GD: Graph Drawing and Network Visualization, Boston, MA, United States, 2018,
vol. 10692, pp. 160–166.'
ista: 'Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD: Graph Drawing
and Network Visualization, LNCS, vol. 10692, 160–166.'
mla: 'Fulek, Radoslav, and János Pach. Thrackles: An Improved Upper Bound.
Vol. 10692, Springer, 2018, pp. 160–66, doi:10.1007/978-3-319-73915-1_14.'
short: R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.
conference:
end_date: 2017-09-27
location: Boston, MA, United States
name: 'GD: Graph Drawing and Network Visualization'
start_date: 201-09-25
corr_author: '1'
date_created: 2018-12-11T11:46:27Z
date_published: 2018-01-21T00:00:00Z
date_updated: 2026-04-16T09:48:11Z
day: '21'
department:
- _id: UlWa
doi: 10.1007/978-3-319-73915-1_14
external_id:
arxiv:
- '1708.08037'
intvolume: ' 10692'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.08037
month: '01'
oa: 1
oa_version: Submitted Version
page: 160 - 166
publication_status: published
publisher: Springer
publist_id: '7390'
quality_controlled: '1'
related_material:
record:
- id: '5857'
relation: later_version
status: public
scopus_import: '1'
status: public
title: 'Thrackles: An improved upper bound'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10692
year: '2018'
...
---
_id: '6774'
abstract:
- lang: eng
text: "A central problem of algebraic topology is to understand the homotopy groups
\ \U0001D70B\U0001D451(\U0001D44B) of a topological space X. For the computational
version of the problem, it is well known that there is no algorithm to decide
whether the fundamental group \U0001D70B1(\U0001D44B) 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 \U0001D70B1(\U0001D44B)
\ trivial), compute the higher homotopy group \U0001D70B\U0001D451(\U0001D44B)
\ for any given \U0001D451≥2 . However, these algorithms come with a caveat:
They compute the isomorphism type of \U0001D70B\U0001D451(\U0001D44B) , \U0001D451≥2
\ as an abstract finitely generated abelian group given by generators and relations,
but they work with very implicit representations of the elements of \U0001D70B\U0001D451(\U0001D44B)
. Converting elements of this abstract group into explicit geometric maps from
the d-dimensional sphere \U0001D446\U0001D451 to X has been one of the main
unsolved problems in the emerging field of computational homotopy theory. Here
we present an algorithm that, given a simply connected space X, computes \U0001D70B\U0001D451(\U0001D44B)
\ and represents its elements as simplicial maps from a suitable triangulation
of the d-sphere \U0001D446\U0001D451 to X. For fixed d, the algorithm runs
in time exponential in size(\U0001D44B) , the number of simplices of X. Moreover,
we prove that this is optimal: For every fixed \U0001D451≥2 , we construct a
family of simply connected spaces X such that for any simplicial map representing
a generator of \U0001D70B\U0001D451(\U0001D44B) , the size of the triangulation
of \U0001D446\U0001D451 on which the map is defined, is exponential in size(\U0001D44B)
."
article_type: original
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Peter
full_name: Franek, Peter
id: 473294AE-F248-11E8-B48F-1D18A9856A87
last_name: Franek
orcid: 0000-0001-8878-8397
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Stephan Y
full_name: Zhechev, Stephan Y
id: 3AA52972-F248-11E8-B48F-1D18A9856A87
last_name: Zhechev
citation:
ama: Filakovský M, Franek P, Wagner U, Zhechev SY. Computing simplicial representatives
of homotopy group elements. Journal of Applied and Computational Topology.
2018;2(3-4):177-231. doi:10.1007/s41468-018-0021-5
apa: Filakovský, M., Franek, P., Wagner, U., & Zhechev, S. Y. (2018). Computing
simplicial representatives of homotopy group elements. Journal of Applied and
Computational Topology. Springer. https://doi.org/10.1007/s41468-018-0021-5
chicago: Filakovský, Marek, Peter Franek, Uli Wagner, and Stephan Y Zhechev. “Computing
Simplicial Representatives of Homotopy Group Elements.” Journal of Applied
and Computational Topology. Springer, 2018. https://doi.org/10.1007/s41468-018-0021-5.
ieee: M. Filakovský, P. Franek, U. Wagner, and S. Y. Zhechev, “Computing simplicial
representatives of homotopy group elements,” Journal of Applied and Computational
Topology, vol. 2, no. 3–4. Springer, pp. 177–231, 2018.
ista: Filakovský M, Franek P, Wagner U, Zhechev SY. 2018. Computing simplicial representatives
of homotopy group elements. Journal of Applied and Computational Topology. 2(3–4),
177–231.
mla: Filakovský, Marek, et al. “Computing Simplicial Representatives of Homotopy
Group Elements.” Journal of Applied and Computational Topology, vol. 2,
no. 3–4, Springer, 2018, pp. 177–231, doi:10.1007/s41468-018-0021-5.
short: M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and
Computational Topology 2 (2018) 177–231.
corr_author: '1'
date_created: 2019-08-08T06:47:40Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2026-04-08T13:56:01Z
day: '01'
ddc:
- '514'
department:
- _id: UlWa
doi: 10.1007/s41468-018-0021-5
file:
- access_level: open_access
checksum: cf9e7fcd2a113dd4828774fc75cdb7e8
content_type: application/pdf
creator: dernst
date_created: 2019-08-08T06:55:21Z
date_updated: 2020-07-14T12:47:40Z
file_id: '6775'
file_name: 2018_JourAppliedComputTopology_Filakovsky.pdf
file_size: 1056278
relation: main_file
file_date_updated: 2020-07-14T12:47:40Z
has_accepted_license: '1'
intvolume: ' 2'
issue: 3-4
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 177-231
project:
- _id: 25F8B9BC-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M01980
name: Robust Invariants of Nonlinear Systems
- _id: 3AC91DDA-15DF-11EA-824D-93A3E7B544D1
call_identifier: FWF
name: FWF Open Access Fund
publication: Journal of Applied and Computational Topology
publication_identifier:
eissn:
- 2367-1734
issn:
- 2367-1726
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
record:
- id: '6681'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Computing simplicial representatives of homotopy group elements
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2
year: '2018'
...
---
_id: '742'
abstract:
- lang: eng
text: 'We give a detailed and easily accessible proof of Gromov’s Topological Overlap
Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral
cell complex of dimension d. Informally, the theorem states that if X has sufficiently
strong higher-dimensional expansion properties (which generalize edge expansion
of graphs and are defined in terms of cellular cochains of X) then X has the following
topological overlap property: for every continuous map (Formula presented.) there
exists a point (Formula presented.) that is contained in the images of a positive
fraction (Formula presented.) of the d-cells of X. More generally, the conclusion
holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear
manifold M, with a constant (Formula presented.) that depends only on d and on
the expansion properties of X, but not on M.'
article_processing_charge: Yes (via OA deal)
author:
- first_name: Dominic
full_name: Dotterrer, Dominic
last_name: Dotterrer
- first_name: Tali
full_name: Kaufman, Tali
last_name: Kaufman
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. Geometriae
Dedicata. 2018;195(1):307–317. doi:10.1007/s10711-017-0291-4
apa: Dotterrer, D., Kaufman, T., & Wagner, U. (2018). On expansion and topological
overlap. Geometriae Dedicata. Springer. https://doi.org/10.1007/s10711-017-0291-4
chicago: Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological
Overlap.” Geometriae Dedicata. Springer, 2018. https://doi.org/10.1007/s10711-017-0291-4.
ieee: D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,”
Geometriae Dedicata, vol. 195, no. 1. Springer, pp. 307–317, 2018.
ista: Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap.
Geometriae Dedicata. 195(1), 307–317.
mla: Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” Geometriae
Dedicata, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:10.1007/s10711-017-0291-4.
short: D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.
corr_author: '1'
date_created: 2018-12-11T11:48:16Z
date_published: 2018-08-01T00:00:00Z
date_updated: 2025-06-03T11:41:00Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.1007/s10711-017-0291-4
external_id:
isi:
- '000437122700017'
file:
- access_level: open_access
checksum: d2f70fc132156504aa4c626aa378a7ab
content_type: application/pdf
creator: kschuh
date_created: 2019-01-15T13:44:05Z
date_updated: 2020-07-14T12:47:58Z
file_id: '5835'
file_name: s10711-017-0291-4.pdf
file_size: 412486
relation: main_file
file_date_updated: 2020-07-14T12:47:58Z
has_accepted_license: '1'
intvolume: ' 195'
isi: 1
issue: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 307–317
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication: Geometriae Dedicata
publication_status: published
publisher: Springer
publist_id: '6925'
pubrep_id: '912'
quality_controlled: '1'
related_material:
record:
- id: '1378'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On expansion and topological overlap
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: 195
year: '2018'
...
---
_id: '1113'
abstract:
- lang: eng
text: 'A drawing of a graph G is radial if the vertices of G are placed on concentric
circles C 1 , . . . , C k with common center c , and edges are drawn radially
: every edge intersects every circle centered at c at most once. G is radial planar
if it has a radial embedding, that is, a crossing-free radial drawing. If the
vertices of G are ordered or partitioned into ordered levels (as they are for
leveled graphs), we require that the assignment of vertices to circles corresponds
to the given ordering or leveling. We show that a graph G is radial planar if
G has a radial drawing in which every two edges cross an even number of times;
the radial embedding has the same leveling as the radial drawing. In other words,
we establish the weak variant of the Hanani-Tutte theorem for radial planarity.
This generalizes a result by Pach and Toth.'
acknowledgement: An earlier version of the paper appeared in the proceedings of Graph
Drawing 2015. The research of the first author has received funding from the People
Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme
(FP7/2007-2013) under REA grant agreement no [291734].
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: Michael
full_name: Pelsmajer, Michael
last_name: Pelsmajer
- first_name: Marcus
full_name: Schaefer, Marcus
last_name: Schaefer
citation:
ama: Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. Journal
of Graph Algorithms and Applications. 2017;21(1):135-154. doi:10.7155/jgaa.00408
apa: Fulek, R., Pelsmajer, M., & Schaefer, M. (2017). Hanani-Tutte for radial
planarity. Journal of Graph Algorithms and Applications. Brown University.
https://doi.org/10.7155/jgaa.00408
chicago: Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte
for Radial Planarity.” Journal of Graph Algorithms and Applications. Brown
University, 2017. https://doi.org/10.7155/jgaa.00408.
ieee: R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,”
Journal of Graph Algorithms and Applications, vol. 21, no. 1. Brown University,
pp. 135–154, 2017.
ista: Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity.
Journal of Graph Algorithms and Applications. 21(1), 135–154.
mla: Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” Journal of
Graph Algorithms and Applications, vol. 21, no. 1, Brown University, 2017,
pp. 135–54, doi:10.7155/jgaa.00408.
short: R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications
21 (2017) 135–154.
date_created: 2018-12-11T11:50:13Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-09-23T09:13:42Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.7155/jgaa.00408
ec_funded: 1
external_id:
arxiv:
- '1608.08662'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-10-24T10:54:37Z
date_updated: 2019-10-24T10:54:37Z
file_id: '6967'
file_name: 2017_JournalGraphAlgorithms_Fulek.pdf
file_size: 573623
relation: main_file
success: 1
file_date_updated: 2019-10-24T10:54:37Z
has_accepted_license: '1'
intvolume: ' 21'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 135 - 154
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of Graph Algorithms and Applications
publication_status: published
publisher: Brown University
publist_id: '6254'
quality_controlled: '1'
related_material:
record:
- id: '1164'
relation: earlier_version
status: public
- id: '1595'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Hanani-Tutte for radial planarity
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2017'
...