---
_id: '6313'
abstract:
- lang: eng
text: We prove three principal results. First we exhibit a drawing of $K_{10}$ in
the plane for which there do not exist extensions of the edges to simple closed
curves with any two curves intersecting at most twice. Second, we exhibit a drawing
of $K_9$ that has an extension of its edges to simple closed curves such that
any two curves intersect in at most two points, but no extension to simple closed
curves has every two curves intersecting in exactly two points. Third, we show
that every h-convex drawing (introduced by Arroyo et al, submitted) has extensions
of its edges to simple closed curves such that any two curves intersect in exactly
two points. Using this result, we show that} a set of three axioms of simple closed
curve extensions characterizes h-convexity.
accept: '1'
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
- first_name: Bruce
full_name: Richter, Bruce
last_name: Richter
- first_name: Matthew
full_name: Sunohara, Matthew
last_name: Sunohara
citation:
ama: Arroyo Guevara AM, Richter B, Sunohara M. Extending drawings of complete graphs
into arrangements of pseudocircles.
apa: Arroyo Guevara, A. M., Richter, B., & Sunohara, M. (n.d.). Extending drawings
of complete graphs into arrangements of pseudocircles.
chicago: Arroyo Guevara, Alan M, Bruce Richter, and Matthew Sunohara. “Extending
Drawings of Complete Graphs into Arrangements of Pseudocircles,” n.d.
ieee: A. M. Arroyo Guevara, B. Richter, and M. Sunohara, “Extending drawings of
complete graphs into arrangements of pseudocircles.” .
ista: Arroyo Guevara AM, Richter B, Sunohara M. Extending drawings of complete graphs
into arrangements of pseudocircles.
mla: Arroyo Guevara, Alan M., et al. *Extending Drawings of Complete Graphs into
Arrangements of Pseudocircles*.
short: A.M. Arroyo Guevara, B. Richter, M. Sunohara, (n.d.).
date_created: 2019-04-16T11:12:27Z
date_published: 2019-04-16T00:00:00Z
date_updated: 2019-08-02T12:39:17Z
day: '16'
ddc:
- '516'
department:
- _id: UlWa
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-04-16T11:15:12Z
date_updated: 2019-04-16T11:15:12Z
file_id: '6315'
file_name: 2019_Draft_Arroyo.pdf
file_size: 964688
open_access: 1
relation: main_file
success: 1
file_date_updated: 2019-04-16T11:15:12Z
language:
- iso: eng
month: '04'
oa: 1
oa_version: Draft
page: '35'
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication_status: draft
status: public
title: Extending drawings of complete graphs into arrangements of pseudocircles
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6647'
abstract:
- lang: eng
text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states
that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition
X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r,
all share a common point. In this paper, we prove a strengthening of this theorem
that guarantees a partition which, in addition to the above, has the property
that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections.
Possible generalizations and algorithmic aspects are also discussed. As a concrete
application, we show that any n points in the plane in general position span floor[n/3]
vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries
have pairwise nonempty intersections; this number is clearly best possible. A
previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing
triangles. Our result generalizes to a result about simplices in R^d,d >=2.
accept: '1'
alternative_title:
- LIPIcs
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Bernd
full_name: Gärtner, Bernd
last_name: Gärtner
- first_name: Andrey
full_name: Kupavskii, Andrey
last_name: Kupavskii
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
cc_license: '''https://creativecommons.org/licenses/by/4.0/'''
citation:
ama: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg
theorem. In: *35th International Symposium on Computational Geometry*. Vol
129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38'
apa: 'Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019).
The crossing Tverberg theorem. In *35th International Symposium on Computational
Geometry* (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38'
chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
Wagner. “The Crossing Tverberg Theorem.” In *35th International Symposium on
Computational Geometry*, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38.
ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
Tverberg theorem,” in *35th International Symposium on Computational Geometry*,
Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.
ista: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg
theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium
on Computational Geometry, LIPIcs, vol. 129. 38:1-38:13.'
mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” *35th International
Symposium on Computational Geometry*, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.
short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International
Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019, p. 38:1-38:13.
conference:
end_date: 2019-06-21
location: Portland, OR, United States
name: 'SoCG 2019: Symposium on Computational Geometry'
start_date: 2019-06-18
date_created: 2019-07-17T10:35:04Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2019-08-02T12:39:24Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.38
external_id:
arxiv:
- '1812.04911'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-07-24T06:54:52Z
date_updated: 2019-07-24T06:54:52Z
file_id: '6667'
file_name: 2019_LIPICS_Fulek.pdf
file_size: 559837
open_access: 1
relation: main_file
success: 1
file_date_updated: 2019-07-24T06:54:52Z
intvolume: ' 129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 38:1-38:13
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771047'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: The crossing Tverberg theorem
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
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."
accept: '1'
article_processing_charge: No
article_type: original
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
cc_license: '''https://creativecommons.org/licenses/by/4.0/'''
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*,
*61*(4), 880–898. 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*
61, no. 4 (2019): 880–98. 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, 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: 2019-09-24T07:18:40Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
external_id:
arxiv:
- '1710.02741'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-02-14T11:57:22Z
date_updated: 2019-02-14T11:57:22Z
file_id: '5988'
file_name: 2018_DiscreteGeometry_Lubiw.pdf
file_size: 556276
open_access: 1
relation: main_file
success: 1
file_date_updated: 2019-02-14T11:57:22Z
intvolume: ' 61'
issue: '4'
language:
- iso: eng
month: '06'
oa_version: Published Version
page: 880-898
project:
- _id: BFDF9788-01D1-11E9-AC17-EBD7A21D5664
name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- 0179-5376
- 1432-0444
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '683'
relation: earlier_version
status: public
status: public
title: A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2019'
...
---
_id: '6681'
abstract:
- lang: eng
text: "The first part of the thesis considers the computational aspects of the homotopy
groups πd(X) of a topological space X. It is well known that there is no algorithm
to decide whether the fundamental group π1(X) of a given finite simplicial complex
X is trivial. On the other hand, there are several algorithms that, given a finite
simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute
the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms
come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract
finitely generated abelian group given by generators and relations, but they work
with very implicit representations of the elements of πd(X). We present an algorithm
that, given a simply connected space X, computes πd(X) and represents its elements
as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed
d, the algorithm runs in time exponential in size(X), the number of simplices
of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct
a family of simply connected spaces X such that for any simplicial map representing
a generator of πd(X), the size of the triangulation of S d on which the map is
defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove
that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋,
k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable
range: Given a finite simplicial complex K of dimension k, decide whether there
exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of
K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space."
accept: '1'
alternative_title:
- IST Austria Thesis
article_processing_charge: No
author:
- first_name: Stephan Y
full_name: Zhechev, Stephan Y
id: 3AA52972-F248-11E8-B48F-1D18A9856A87
last_name: Zhechev
cc_license: '''https://creativecommons.org/licenses/by/4.0/'''
citation:
ama: Zhechev SY. *Algorithmic Aspects of Homotopy Theory and Embeddability*.
IST Austria; 2019. doi:10.15479/AT:ISTA:6681
apa: Zhechev, S. Y. (2019). *Algorithmic aspects of homotopy theory and embeddability*.
IST Austria. https://doi.org/10.15479/AT:ISTA:6681
chicago: Zhechev, Stephan Y. *Algorithmic Aspects of Homotopy Theory and Embeddability*.
IST Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.
ieee: S. Y. Zhechev, *Algorithmic aspects of homotopy theory and embeddability*.
IST Austria, 2019.
ista: Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability,
IST Austria, 104p.
mla: Zhechev, Stephan Y. *Algorithmic Aspects of Homotopy Theory and Embeddability*.
IST Austria, 2019, doi:10.15479/AT:ISTA:6681.
short: S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, IST
Austria, 2019.
date_created: 2019-07-26T11:14:34Z
date_published: 2019-08-08T00:00:00Z
date_updated: 2019-09-27T08:48:09Z
day: '08'
ddc:
- '514'
department:
- _id: UlWa
doi: 10.15479/AT:ISTA:6681
file:
- access_level: open_access
content_type: application/pdf
creator: szhechev
date_created: 2019-08-07T13:02:50Z
date_updated: 2019-08-07T13:02:50Z
file_id: '6771'
file_name: Stephan_Zhechev_thesis.pdf
file_size: 1464227
open_access: 1
relation: main_file
request_a_copy: 0
- access_level: closed
content_type: application/octet-stream
creator: szhechev
date_created: 2019-08-07T13:03:22Z
date_updated: 2019-08-08T06:41:37Z
file_id: '6772'
file_name: Stephan_Zhechev_thesis.tex
file_size: 303988
open_access: 0
relation: source_file
request_a_copy: 0
- access_level: closed
content_type: application/zip
creator: szhechev
date_created: 2019-08-07T13:03:34Z
date_updated: 2019-08-08T06:41:37Z
file_id: '6773'
file_name: supplementary_material.zip
file_size: 1087004
open_access: 0
relation: supplementary_material
request_a_copy: 0
file_date_updated: 2019-08-08T06:41:37Z
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '104'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: IST 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
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6556'
abstract:
- lang: eng
text: 'Motivated by fixed-parameter tractable (FPT) problems in computational topology,
we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined
to be the minimum treewidth of the face pairing graph of any triangulation T of
M. In this setting the relationship between the topology of a 3-manifold and its
treewidth is of particular interest. First, as a corollary of work of Jaco and
Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth
tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination
with our earlier work with Wagner, this yields that for non-Haken manifolds the
Heegaard genus and the treewidth are within a constant factor. Second, we characterize
all 3-manifolds of treewidth one: These are precisely the lens spaces and a single
other Seifert fibered space. Furthermore, we show that all remaining orientable
Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth
two. In particular, for every spherical 3-manifold we exhibit a triangulation
of treewidth at most two. Our results further validate the parameter of treewidth
(and other related parameters such as cutwidth or congestion) to be useful for
topological computing, and also shed more light on the scope of existing FPT-algorithms
in the field.'
accept: '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
cc_license: '''https://creativecommons.org/licenses/by/4.0/'''
citation:
ama: 'Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: *35th
International Symposium on Computational Geometry (SoCG 2019)*. Vol 129. Leibniz
International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum
fuer 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 (SoCG
2019)* (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss
Dagstuhl - Leibniz-Zentrum fuer 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 (SoCG
2019)*, 129:44:1-44:20. Leibniz International Proceedings in Informatics (LIPIcs).
Schloss Dagstuhl - Leibniz-Zentrum fuer 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 (SoCG 2019)*,
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 2019). SoCG: Symposium
on Computational GeometryLeibniz International Proceedings in Informatics (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 (SoCG 2019)*,
vol. 129, Schloss Dagstuhl - Leibniz-Zentrum fuer 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 (SoCG 2019), Schloss Dagstuhl - Leibniz-Zentrum fuer 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: 2019-08-02T12:39:22Z
day: '01'
ddc:
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2019.44
external_id:
arxiv:
- '1812.05528'
file:
- access_level: open_access
content_type: application/pdf
creator: kschuh
date_created: 2019-06-12T06:45:33Z
date_updated: 2019-06-12T06:45:33Z
file_id: '6557'
file_name: 2019_LIPIcs-Huszar.pdf
file_size: 905885
open_access: 1
relation: main_file
success: 1
file_date_updated: 2019-06-12T06:45:33Z
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 (SoCG 2019)
publication_identifier:
isbn:
- 978-3-95977-104-7
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
quality_controlled: '1'
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: 3-manifold triangulations with small treewidth
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...
---
_id: '6563'
abstract:
- lang: eng
text: "This paper presents two algorithms. The first decides the existence of a
pointed homotopy between given simplicial maps \U0001D453,\U0001D454:\U0001D44B→\U0001D44C,
and the second computes the group [\U0001D6F4\U0001D44B,\U0001D44C]∗ of pointed
homotopy classes of maps from a suspension; in both cases, the target Y is assumed
simply connected. More generally, these algorithms work relative to \U0001D434⊆\U0001D44B."
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Lukas
full_name: Vokřínek, Lukas
last_name: Vokřínek
citation:
ama: Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint.
*Foundations of Computational Mathematics*. 2019. doi:10.1007/s10208-019-09419-x
apa: Filakovský, M., & Vokřínek, L. (2019). Are two given maps homotopic? An
algorithmic viewpoint. *Foundations of Computational Mathematics*. https://doi.org/10.1007/s10208-019-09419-x
chicago: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An
Algorithmic Viewpoint.” *Foundations of Computational Mathematics*, 2019.
https://doi.org/10.1007/s10208-019-09419-x.
ieee: M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic
viewpoint,” *Foundations of Computational Mathematics*, 2019.
ista: Filakovský M, Vokřínek L. 2019. Are two given maps homotopic? An algorithmic
viewpoint. Foundations of Computational Mathematics.
mla: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic
Viewpoint.” *Foundations of Computational Mathematics*, Springer Nature,
2019, doi:10.1007/s10208-019-09419-x.
short: M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics (2019).
date_created: 2019-06-16T21:59:14Z
date_published: 2019-05-29T00:00:00Z
date_updated: 2019-08-02T12:39:22Z
day: '29'
department:
- _id: UlWa
doi: 10.1007/s10208-019-09419-x
external_id:
arxiv:
- '1312.2337'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1312.2337
month: '05'
oa: 1
oa_version: Preprint
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- '16153383'
issn:
- '16153375'
publication_status: epub_ahead
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Are two given maps homotopic? An algorithmic viewpoint
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6638'
abstract:
- lang: eng
text: The crossing number of a graph G is the least number of crossings over all
possible drawings of G. We present a structural characterization of graphs with
crossing number one.
author:
- first_name: 'André '
full_name: 'Silva, André '
last_name: Silva
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
- first_name: Bruce
full_name: Richter, Bruce
last_name: Richter
- first_name: Orlando
full_name: Lee, Orlando
last_name: Lee
citation:
ama: Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing.
*Discrete Mathematics*. 2019. doi:10.1016/j.disc.2019.06.031
apa: Silva, A., Arroyo Guevara, A. M., Richter, B., & Lee, O. (2019). Graphs
with at most one crossing. *Discrete Mathematics*. https://doi.org/10.1016/j.disc.2019.06.031
chicago: Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs
with at Most One Crossing.” *Discrete Mathematics*, 2019. https://doi.org/10.1016/j.disc.2019.06.031.
ieee: A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most
one crossing,” *Discrete Mathematics*, 2019.
ista: Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one
crossing. Discrete Mathematics.
mla: Silva, André, et al. “Graphs with at Most One Crossing.” *Discrete Mathematics*,
Elsevier, 2019, doi:10.1016/j.disc.2019.06.031.
short: A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics (2019).
date_created: 2019-07-14T21:59:20Z
date_published: 2019-07-03T00:00:00Z
date_updated: 2019-08-02T12:39:24Z
day: '03'
department:
- _id: UlWa
doi: 10.1016/j.disc.2019.06.031
external_id:
arxiv:
- '1901.09955'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1901.09955
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 26366136-B435-11E9-9278-68D0E5697425
name: Reglas de Conectividad funcional en el hipocampo
- _id: 260C2330-B435-11E9-9278-68D0E5697425
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Discrete Mathematics
publication_status: epub_ahead
publisher: Elsevier
quality_controlled: '1'
status: public
title: Graphs with at most one crossing
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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.'
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*, *259*(4), 266–231. 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* 259, no. 4 (2019): 266–231. 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, 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: 2019-09-19T10:47:14Z
day: '30'
department:
- _id: UlWa
doi: 10.1016/j.dam.2018.12.025
intvolume: ' 259'
issue: '4'
language:
- iso: eng
month: '04'
oa_version: None
page: 266-231
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
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
status: public
title: 'Thrackles: An improved upper bound'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 259
year: '2019'
...
---
_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
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:401-4014. doi:10.4230/LIPIcs.SoCG.2018.40'
apa: 'Fulek, R., & Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol.
99, pp. 401–4014). 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:401–4014.
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,
pp. 401–4014.'
ista: 'Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium
on Computational Geometry, LIPIcs, vol. 99. 401–4014.'
mla: Fulek, Radoslav, and Jan Kynčl. *The ℤ2-Genus of Kuratowski Minors*. Vol.
99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 401–4014, doi:10.4230/LIPIcs.SoCG.2018.40.
short: R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2018, pp. 401–4014.
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: 2019-08-02T12:37:28Z
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: 401 - 4014
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
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'
status: public
title: The ℤ2-Genus of Kuratowski minors
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 99
year: '2018'
...
---
_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.
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*. 2018. doi:10.1002/jgt.22436
apa: Chaplick, S., Fulek, R., & Klavík, P. (2018). Extending partial representations
of circle graphs. *Journal of Graph Theory*. 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*, 2018. 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*, 2018.
ista: Chaplick S, Fulek R, Klavík P. 2018. Extending partial representations of
circle graphs. Journal of Graph Theory.
mla: Chaplick, Steven, et al. “Extending Partial Representations of Circle Graphs.”
*Journal of Graph Theory*, Wiley, 2018, doi:10.1002/jgt.22436.
short: S. Chaplick, R. Fulek, P. Klavík, Journal of Graph Theory (2018).
date_created: 2018-12-30T22:59:15Z
date_published: 2018-12-17T00:00:00Z
date_updated: 2019-08-02T12:39:04Z
day: '17'
department:
- _id: UlWa
doi: 10.1002/jgt.22436
external_id:
arxiv:
- '1309.2399'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1309.2399
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of Graph Theory
publication_identifier:
issn:
- '03649024'
publication_status: epub_ahead
publisher: Wiley
quality_controlled: '1'
status: public
title: Extending partial representations of circle graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2018'
...