---
_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: 2023-09-06T11:10:58Z
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/pdf/1711.08436.pdf
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
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: 2023-09-06T14:56:00Z
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
date_created: 2020-01-29T16:17:05Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2021-01-12T08:13:24Z
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: '5790'
abstract:
- lang: eng
text: The partial representation extension problem is a recently introduced generalization
of the recognition problem. A circle graph is an intersection graph of chords
of a circle. We study the partial representation extension problem for circle
graphs, where the input consists of a graph G and a partial representation R′
giving some predrawn chords that represent an induced subgraph of G. The question
is whether one can extend R′ to a representation R of the entire graph G, that
is, whether one can draw the remaining chords into a partially predrawn representation
to obtain a representation of G. Our main result is an O(n3) time algorithm for
partial representation extension of circle graphs, where n is the number of vertices.
To show this, we describe the structure of all representations of a circle graph
using split decomposition. This can be of independent interest.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Steven
full_name: Chaplick, Steven
last_name: Chaplick
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Pavel
full_name: Klavík, Pavel
last_name: Klavík
citation:
ama: Chaplick S, Fulek R, Klavík P. Extending partial representations of circle
graphs. Journal of Graph Theory. 2019;91(4):365-394. doi:10.1002/jgt.22436
apa: Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations
of circle graphs. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22436
chicago: Chaplick, Steven, Radoslav Fulek, and Pavel Klavík. “Extending Partial
Representations of Circle Graphs.” Journal of Graph Theory. Wiley, 2019.
https://doi.org/10.1002/jgt.22436.
ieee: S. Chaplick, R. Fulek, and P. Klavík, “Extending partial representations of
circle graphs,” Journal of Graph Theory, vol. 91, no. 4. Wiley, pp. 365–394,
2019.
ista: Chaplick S, Fulek R, Klavík P. 2019. Extending partial representations of
circle graphs. Journal of Graph Theory. 91(4), 365–394.
mla: Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.”
Journal of Graph Theory, vol. 91, no. 4, Wiley, 2019, pp. 365–94, doi:10.1002/jgt.22436.
short: S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory 91 (2019) 365–394.
date_created: 2018-12-30T22:59:15Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-08-24T14:30:43Z
day: '01'
department:
- _id: UlWa
doi: 10.1002/jgt.22436
ec_funded: 1
external_id:
arxiv:
- '1309.2399'
isi:
- '000485392800004'
intvolume: ' 91'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1309.2399
month: '08'
oa: 1
oa_version: Preprint
page: 365-394
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of Graph Theory
publication_identifier:
issn:
- '03649024'
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending partial representations of circle graphs
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 91
year: '2019'
...
---
_id: '5857'
abstract:
- lang: eng
text: 'A thrackle is a graph drawn in the plane so that every pair of its edges
meet exactly once: either at a common end vertex or in a proper crossing. We prove
that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are
defined similarly, except that every pair of edges that do not share a vertex
are allowed to cross an odd number of times. It is also shown that the maximum
number of edges of a quasi-thrackle on n vertices is [Formula presented](n−1),
and that this bound is best possible for infinitely many values of n.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: János
full_name: Pach, János
last_name: Pach
citation:
ama: 'Fulek R, Pach J. Thrackles: An improved upper bound. Discrete Applied Mathematics.
2019;259(4):266-231. doi:10.1016/j.dam.2018.12.025'
apa: 'Fulek, R., & Pach, J. (2019). Thrackles: An improved upper bound. Discrete
Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2018.12.025'
chicago: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.”
Discrete Applied Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.dam.2018.12.025.'
ieee: 'R. Fulek and J. Pach, “Thrackles: An improved upper bound,” Discrete Applied
Mathematics, vol. 259, no. 4. Elsevier, pp. 266–231, 2019.'
ista: 'Fulek R, Pach J. 2019. Thrackles: An improved upper bound. Discrete Applied
Mathematics. 259(4), 266–231.'
mla: 'Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound.” Discrete
Applied Mathematics, vol. 259, no. 4, Elsevier, 2019, pp. 266–231, doi:10.1016/j.dam.2018.12.025.'
short: R. Fulek, J. Pach, Discrete Applied Mathematics 259 (2019) 266–231.
date_created: 2019-01-20T22:59:17Z
date_published: 2019-04-30T00:00:00Z
date_updated: 2023-08-24T14:39:33Z
day: '30'
department:
- _id: UlWa
doi: 10.1016/j.dam.2018.12.025
external_id:
arxiv:
- '1708.08037'
isi:
- '000466061100020'
intvolume: ' 259'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.08037
month: '04'
oa: 1
oa_version: Preprint
page: 266-231
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '433'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: 'Thrackles: An improved upper bound'
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 259
year: '2019'
...
---
_id: '5986'
abstract:
- lang: eng
text: "Given a triangulation of a point set in the plane, a flip deletes an edge
e whose removal leaves a convex quadrilateral, and replaces e by the opposite
diagonal of the quadrilateral. It is well known that any triangulation of a point
set can be reconfigured to any other triangulation by some sequence of flips.
We explore this question in the setting where each edge of a triangulation has
a label, and a flip transfers the label of the removed edge to the new edge. It
is not true that every labelled triangulation of a point set can be reconfigured
to every other labelled triangulation via a sequence of flips, but we characterize
when this is possible. There is an obvious necessary condition: for each label
l, if edge e has label l in the first triangulation and edge f has label l in
the second triangulation, then there must be some sequence of flips that moves
label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot
formulated the Orbit Conjecture, which states that this necessary condition is
also sufficient, i.e. that all labels can be simultaneously mapped to their destination
if and only if each label individually can be mapped to its destination. We prove
this conjecture. Furthermore, we give a polynomial-time algorithm (with \U0001D442(\U0001D45B8)
being a crude bound on the run-time) to find a sequence of flips to reconfigure
one labelled triangulation to another, if such a sequence exists, and we prove
an upper bound of \U0001D442(\U0001D45B7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges
on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional
ball (this follows from a result of Orden and Santos; we give a different proof
based on a shelling argument). The dual cell complex of this simplicial ball,
called the flip complex, has the usual flip graph as its 1-skeleton. We use properties
of the 2-skeleton of the flip complex to prove the Orbit Conjecture."
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 2019;61(4):880-898.
doi:10.1007/s00454-018-0035-8
apa: Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture
for flipping edge-labelled triangulations. Discrete & Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-018-0035-8
chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry.
Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.
ieee: A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for
flipping edge-labelled triangulations,” Discrete & Computational Geometry,
vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.
ista: Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.
mla: Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled
Triangulations.” Discrete & Computational Geometry, vol. 61, no. 4,
Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.
short: A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61
(2019) 880–898.
date_created: 2019-02-14T11:54:08Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:17:36Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
external_id:
arxiv:
- '1710.02741'
isi:
- '000466130000009'
file:
- access_level: open_access
checksum: e1bff88f1d77001b53b78c485ce048d7
content_type: application/pdf
creator: dernst
date_created: 2019-02-14T11:57:22Z
date_updated: 2020-07-14T12:47:14Z
file_id: '5988'
file_name: 2018_DiscreteGeometry_Lubiw.pdf
file_size: 556276
relation: main_file
file_date_updated: 2020-07-14T12:47:14Z
has_accepted_license: '1'
intvolume: ' 61'
isi: 1
issue: '4'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 880-898
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '683'
relation: earlier_version
status: public
- id: '7944'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: A proof of the orbit conjecture for flipping edge-labelled triangulations
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 61
year: '2019'
...
---
_id: '6556'
abstract:
- lang: eng
text: 'Motivated by fixed-parameter tractable (FPT) problems in computational topology,
we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined
to be the minimum treewidth of the face pairing graph of any triangulation T of
M. In this setting the relationship between the topology of a 3-manifold and its
treewidth is of particular interest. First, as a corollary of work of Jaco and
Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth
tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination
with our earlier work with Wagner, this yields that for non-Haken manifolds the
Heegaard genus and the treewidth are within a constant factor. Second, we characterize
all 3-manifolds of treewidth one: These are precisely the lens spaces and a single
other Seifert fibered space. Furthermore, we show that all remaining orientable
Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth
two. In particular, for every spherical 3-manifold we exhibit a triangulation
of treewidth at most two. Our results further validate the parameter of treewidth
(and other related parameters such as cutwidth or congestion) to be useful for
topological computing, and also shed more light on the scope of existing FPT-algorithms
in the field.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Kristóf
full_name: Huszár, Kristóf
id: 33C26278-F248-11E8-B48F-1D18A9856A87
last_name: Huszár
orcid: 0000-0002-5445-5057
- first_name: Jonathan
full_name: Spreer, Jonathan
last_name: Spreer
citation:
ama: 'Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th
International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44'
apa: 'Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small
treewidth. In 35th International Symposium on Computational Geometry (Vol.
129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44'
chicago: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
Treewidth.” In 35th International Symposium on Computational Geometry,
129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.
ieee: K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,”
in 35th International Symposium on Computational Geometry, Portland, Oregon,
United States, 2019, vol. 129, p. 44:1-44:20.
ista: 'Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth.
35th International Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, LIPIcs, vol. 129, 44:1-44:20.'
mla: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
Treewidth.” 35th International Symposium on Computational Geometry, vol.
129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44.
short: K. Huszár, J. Spreer, in:, 35th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.
conference:
end_date: 2019-06-21
location: Portland, Oregon, United States
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2019-06-18
date_created: 2019-06-11T20:09:57Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:18:26Z
day: '01'
ddc:
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2019.44
external_id:
arxiv:
- '1812.05528'
file:
- access_level: open_access
checksum: 29d18c435368468aa85823dabb157e43
content_type: application/pdf
creator: kschuh
date_created: 2019-06-12T06:45:33Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6557'
file_name: 2019_LIPIcs-Huszar.pdf
file_size: 905885
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 129'
keyword:
- computational 3-manifold topology
- fixed-parameter tractability
- layered triangulations
- structural graph theory
- treewidth
- cutwidth
- Heegaard genus
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 44:1-44:20
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- 978-3-95977-104-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '8032'
relation: part_of_dissertation
status: public
scopus_import: '1'
status: public
title: 3-manifold triangulations with small treewidth
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...
---
_id: '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: 2023-09-06T11:13:41Z
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:
- '18688969'
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: '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: 2023-09-15T12:19:32Z
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: '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: 2023-09-06T11:10:57Z
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: '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: 2023-08-14T12:43:51Z
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: '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.
date_created: 2019-08-08T06:47:40Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-09-07T13:10:36Z
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
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.
date_created: 2018-12-11T11:48:16Z
date_published: 2018-08-01T00:00:00Z
date_updated: 2023-09-27T12:29:57Z
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: '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 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 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. 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: 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: 2023-09-11T12:49:55Z
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
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
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).
date_created: 2019-04-30T06:09:57Z
date_published: 2018-05-31T00:00:00Z
date_updated: 2023-09-19T14:50:12Z
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: '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: 2023-09-11T13:38:49Z
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
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 2017: 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 2017: 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 2017: 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 2017: Graph Drawing and Network Visualization'
start_date: 201-09-25
date_created: 2018-12-11T11:46:27Z
date_published: 2018-01-21T00:00:00Z
date_updated: 2023-08-24T14:39:32Z
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: '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'
...