---
_id: '1113'
abstract:
- lang: eng
text: 'A drawing of a graph G is radial if the vertices of G are placed on concentric
circles C 1 , . . . , C k with common center c , and edges are drawn radially
: every edge intersects every circle centered at c at most once. G is radial planar
if it has a radial embedding, that is, a crossing-free radial drawing. If the
vertices of G are ordered or partitioned into ordered levels (as they are for
leveled graphs), we require that the assignment of vertices to circles corresponds
to the given ordering or leveling. We show that a graph G is radial planar if
G has a radial drawing in which every two edges cross an even number of times;
the radial embedding has the same leveling as the radial drawing. In other words,
we establish the weak variant of the Hanani-Tutte theorem for radial planarity.
This generalizes a result by Pach and Toth.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Michael
full_name: Pelsmajer, Michael
last_name: Pelsmajer
- first_name: Marcus
full_name: Schaefer, Marcus
last_name: Schaefer
citation:
ama: Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. Journal
of Graph Algorithms and Applications. 2017;21(1):135-154. doi:10.7155/jgaa.00408
apa: Fulek, R., Pelsmajer, M., & Schaefer, M. (2017). Hanani-Tutte for radial
planarity. Journal of Graph Algorithms and Applications. Brown University.
https://doi.org/10.7155/jgaa.00408
chicago: Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte
for Radial Planarity.” Journal of Graph Algorithms and Applications. Brown
University, 2017. https://doi.org/10.7155/jgaa.00408.
ieee: R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,”
Journal of Graph Algorithms and Applications, vol. 21, no. 1. Brown University,
pp. 135–154, 2017.
ista: Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity.
Journal of Graph Algorithms and Applications. 21(1), 135–154.
mla: Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” Journal of
Graph Algorithms and Applications, vol. 21, no. 1, Brown University, 2017,
pp. 135–54, doi:10.7155/jgaa.00408.
short: R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications
21 (2017) 135–154.
date_created: 2018-12-11T11:50:13Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-02-23T10:05:57Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.7155/jgaa.00408
ec_funded: 1
external_id:
arxiv:
- '1608.08662'
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-10-24T10:54:37Z
date_updated: 2019-10-24T10:54:37Z
file_id: '6967'
file_name: 2017_JournalGraphAlgorithms_Fulek.pdf
file_size: 573623
relation: main_file
success: 1
file_date_updated: 2019-10-24T10:54:37Z
has_accepted_license: '1'
intvolume: ' 21'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 135 - 154
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of Graph Algorithms and Applications
publication_status: published
publisher: Brown University
publist_id: '6254'
quality_controlled: '1'
related_material:
record:
- id: '1164'
relation: earlier_version
status: public
- id: '1595'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Hanani-Tutte for radial planarity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2017'
...
---
_id: '793'
abstract:
- lang: eng
text: 'Let P be a finite point set in the plane. A cordinary triangle in P is a
subset of P consisting of three non-collinear points such that each of the three
lines determined by the three points contains at most c points of P . Motivated
by a question of Erdös, and answering a question of de Zeeuw, we prove that there
exists a constant c > 0such that P contains a c-ordinary triangle, provided
that P is not contained in the union of two lines. Furthermore, the number of
c-ordinary triangles in P is Ω(| P |). '
article_processing_charge: No
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Hossein
full_name: Mojarrad, Hossein
last_name: Mojarrad
- first_name: Márton
full_name: Naszódi, Márton
last_name: Naszódi
- first_name: József
full_name: Solymosi, József
last_name: Solymosi
- first_name: Sebastian
full_name: Stich, Sebastian
last_name: Stich
- first_name: May
full_name: Szedlák, May
last_name: Szedlák
citation:
ama: 'Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. On the existence
of ordinary triangles. Computational Geometry: Theory and Applications.
2017;66:28-31. doi:10.1016/j.comgeo.2017.07.002'
apa: 'Fulek, R., Mojarrad, H., Naszódi, M., Solymosi, J., Stich, S., & Szedlák,
M. (2017). On the existence of ordinary triangles. Computational Geometry:
Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2017.07.002'
chicago: 'Fulek, Radoslav, Hossein Mojarrad, Márton Naszódi, József Solymosi, Sebastian
Stich, and May Szedlák. “On the Existence of Ordinary Triangles.” Computational
Geometry: Theory and Applications. Elsevier, 2017. https://doi.org/10.1016/j.comgeo.2017.07.002.'
ieee: 'R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, and M. Szedlák,
“On the existence of ordinary triangles,” Computational Geometry: Theory and
Applications, vol. 66. Elsevier, pp. 28–31, 2017.'
ista: 'Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. 2017. On
the existence of ordinary triangles. Computational Geometry: Theory and Applications.
66, 28–31.'
mla: 'Fulek, Radoslav, et al. “On the Existence of Ordinary Triangles.” Computational
Geometry: Theory and Applications, vol. 66, Elsevier, 2017, pp. 28–31, doi:10.1016/j.comgeo.2017.07.002.'
short: 'R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, M. Szedlák, Computational
Geometry: Theory and Applications 66 (2017) 28–31.'
date_created: 2018-12-11T11:48:32Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-27T12:15:16Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.comgeo.2017.07.002
ec_funded: 1
external_id:
isi:
- '000412039700003'
intvolume: ' 66'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1701.08183
month: '01'
oa: 1
oa_version: Submitted Version
page: 28 - 31
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- '09257721'
publication_status: published
publisher: Elsevier
publist_id: '6861'
quality_controlled: '1'
status: public
title: On the existence of ordinary triangles
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2017'
...
---
_id: '794'
abstract:
- lang: eng
text: We show that c-planarity is solvable in quadratic time for flat clustered
graphs with three clusters if the combinatorial embedding of the underlying graph
is fixed. In simpler graph-theoretical terms our result can be viewed as follows.
Given a graph G with the vertex set partitioned into three parts embedded on a
2-sphere, our algorithm decides if we can augment G by adding edges without creating
an edge-crossing so that in the resulting spherical graph the vertices of each
part induce a connected sub-graph. We proceed by a reduction to the problem of
testing the existence of a perfect matching in planar bipartite graphs. We formulate
our result in a slightly more general setting of cyclic clustered graphs, i.e.,
the simple graph obtained by contracting each cluster, where we disregard loops
and multi-edges, is a cycle.
acknowledgement: I would like to thank Jan Kynčl, Dömötör Pálvölgyi and anonymous
referees for many comments and suggestions that helped to improve the presentation
of the result.
article_processing_charge: No
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. C-planarity of embedded cyclic c-graphs. Computational Geometry:
Theory and Applications. 2017;66:1-13. doi:10.1016/j.comgeo.2017.06.016'
apa: 'Fulek, R. (2017). C-planarity of embedded cyclic c-graphs. Computational
Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2017.06.016'
chicago: 'Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational
Geometry: Theory and Applications. Elsevier, 2017. https://doi.org/10.1016/j.comgeo.2017.06.016.'
ieee: 'R. Fulek, “C-planarity of embedded cyclic c-graphs,” Computational Geometry:
Theory and Applications, vol. 66. Elsevier, pp. 1–13, 2017.'
ista: 'Fulek R. 2017. C-planarity of embedded cyclic c-graphs. Computational Geometry:
Theory and Applications. 66, 1–13.'
mla: 'Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” Computational
Geometry: Theory and Applications, vol. 66, Elsevier, 2017, pp. 1–13, doi:10.1016/j.comgeo.2017.06.016.'
short: 'R. Fulek, Computational Geometry: Theory and Applications 66 (2017) 1–13.'
date_created: 2018-12-11T11:48:32Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2023-09-27T12:14:49Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.comgeo.2017.06.016
external_id:
isi:
- '000412039700001'
intvolume: ' 66'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.01346
month: '12'
oa: 1
oa_version: Preprint
page: 1 - 13
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '6860'
quality_controlled: '1'
related_material:
record:
- id: '1165'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: C-planarity of embedded cyclic c-graphs
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2017'
...
---
_id: '795'
abstract:
- lang: eng
text: 'We introduce a common generalization of the strong Hanani–Tutte theorem and
the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where
every pair of independent edges crosses an even number of times, then G has a
planar drawing preserving the rotation of each vertex whose incident edges cross
each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte
theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler
proof.'
article_number: P3.18
article_processing_charge: No
article_type: original
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
- first_name: Dömötör
full_name: Pálvölgyi, Dömötör
last_name: Pálvölgyi
citation:
ama: Fulek R, Kynčl J, Pálvölgyi D. Unified Hanani Tutte theorem. Electronic
Journal of Combinatorics. 2017;24(3). doi:10.37236/6663
apa: Fulek, R., Kynčl, J., & Pálvölgyi, D. (2017). Unified Hanani Tutte theorem.
Electronic Journal of Combinatorics. International Press. https://doi.org/10.37236/6663
chicago: Fulek, Radoslav, Jan Kynčl, and Dömötör Pálvölgyi. “Unified Hanani Tutte
Theorem.” Electronic Journal of Combinatorics. International Press, 2017.
https://doi.org/10.37236/6663.
ieee: R. Fulek, J. Kynčl, and D. Pálvölgyi, “Unified Hanani Tutte theorem,” Electronic
Journal of Combinatorics, vol. 24, no. 3. International Press, 2017.
ista: Fulek R, Kynčl J, Pálvölgyi D. 2017. Unified Hanani Tutte theorem. Electronic
Journal of Combinatorics. 24(3), P3.18.
mla: Fulek, Radoslav, et al. “Unified Hanani Tutte Theorem.” Electronic Journal
of Combinatorics, vol. 24, no. 3, P3.18, International Press, 2017, doi:10.37236/6663.
short: R. Fulek, J. Kynčl, D. Pálvölgyi, Electronic Journal of Combinatorics 24
(2017).
date_created: 2018-12-11T11:48:32Z
date_published: 2017-07-28T00:00:00Z
date_updated: 2022-03-18T12:58:53Z
day: '28'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.37236/6663
ec_funded: 1
file:
- access_level: open_access
checksum: ef320cff0f062051e858f929be6a3581
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T14:04:08Z
date_updated: 2020-07-14T12:48:06Z
file_id: '5853'
file_name: 2017_ElectrCombi_Fulek.pdf
file_size: 236944
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 24'
issue: '3'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Electronic Journal of Combinatorics
publication_identifier:
issn:
- '10778926'
publication_status: published
publisher: International Press
publist_id: '6859'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unified Hanani Tutte theorem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2017'
...
---
_id: '683'
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 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 O(n7) 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.'
alternative_title:
- LIPIcs
article_number: '49'
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. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2017. doi:10.4230/LIPIcs.SoCG.2017.49'
apa: 'Lubiw, A., Masárová, Z., & Wagner, U. (2017). A proof of the orbit conjecture
for flipping edge labelled triangulations (Vol. 77). Presented at the SoCG: Symposium
on Computational Geometry, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.49'
chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
for Flipping Edge Labelled Triangulations,” Vol. 77. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.49.
ieee: 'A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for
flipping edge labelled triangulations,” presented at the SoCG: Symposium on Computational
Geometry, Brisbane, Australia, 2017, vol. 77.'
ista: 'Lubiw A, Masárová Z, Wagner U. 2017. A proof of the orbit conjecture for
flipping edge labelled triangulations. SoCG: Symposium on Computational Geometry,
LIPIcs, vol. 77, 49.'
mla: Lubiw, Anna, et al. A Proof of the Orbit Conjecture for Flipping Edge Labelled
Triangulations. Vol. 77, 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017, doi:10.4230/LIPIcs.SoCG.2017.49.
short: A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017.
conference:
end_date: 2017-07-07
location: Brisbane, Australia
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2017-07-04
date_created: 2018-12-11T11:47:54Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-05T15:01:43Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2017.49
file:
- access_level: open_access
checksum: 24fdde981cc513352a78dcf9b0660ae9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:12Z
date_updated: 2020-07-14T12:47:41Z
file_id: '5265'
file_name: IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf
file_size: 710007
relation: main_file
file_date_updated: 2020-07-14T12:47:41Z
has_accepted_license: '1'
intvolume: ' 77'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7033'
pubrep_id: '896'
quality_controlled: '1'
related_material:
record:
- id: '5986'
relation: later_version
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2017'
...
---
_id: '688'
abstract:
- lang: eng
text: 'We show that the framework of topological data analysis can be extended from
metrics to general Bregman divergences, widening the scope of possible applications.
Examples are the Kullback - Leibler divergence, which is commonly used for comparing
text and images, and the Itakura - Saito divergence, popular for speech and sound.
In particular, we prove that appropriately generalized čech and Delaunay (alpha)
complexes capture the correct homotopy type, namely that of the corresponding
union of Bregman balls. Consequently, their filtrations give the correct persistence
diagram, namely the one generated by the uniformly growing Bregman balls. Moreover,
we show that unlike the metric setting, the filtration of Vietoris-Rips complexes
may fail to approximate the persistence diagram. We propose algorithms to compute
the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally
test their efficiency. Lastly, we explain their surprisingly good performance
by making a connection with discrete Morse theory. '
alternative_title:
- LIPIcs
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
citation:
ama: 'Edelsbrunner H, Wagner H. Topological data analysis with Bregman divergences.
In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:391-3916.
doi:10.4230/LIPIcs.SoCG.2017.39'
apa: 'Edelsbrunner, H., & Wagner, H. (2017). Topological data analysis with
Bregman divergences (Vol. 77, pp. 391–3916). Presented at the Symposium on Computational
Geometry, SoCG, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2017.39'
chicago: Edelsbrunner, Herbert, and Hubert Wagner. “Topological Data Analysis with
Bregman Divergences,” 77:391–3916. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.39.
ieee: H. Edelsbrunner and H. Wagner, “Topological data analysis with Bregman divergences,”
presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia,
2017, vol. 77, pp. 391–3916.
ista: Edelsbrunner H, Wagner H. 2017. Topological data analysis with Bregman divergences.
Symposium on Computational Geometry, SoCG, LIPIcs, vol. 77, 391–3916.
mla: Edelsbrunner, Herbert, and Hubert Wagner. Topological Data Analysis with
Bregman Divergences. Vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017, pp. 391–3916, doi:10.4230/LIPIcs.SoCG.2017.39.
short: H. Edelsbrunner, H. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017, pp. 391–3916.
conference:
end_date: 2017-07-07
location: Brisbane, Australia
name: Symposium on Computational Geometry, SoCG
start_date: 2017-07-04
date_created: 2018-12-11T11:47:56Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2021-01-12T08:09:26Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: HeEd
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2017.39
file:
- access_level: open_access
checksum: 067ab0cb3f962bae6c3af6bf0094e0f3
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:03Z
date_updated: 2020-07-14T12:47:42Z
file_id: '4856'
file_name: IST-2017-895-v1+1_LIPIcs-SoCG-2017-39.pdf
file_size: 990546
relation: main_file
file_date_updated: 2020-07-14T12:47:42Z
has_accepted_license: '1'
intvolume: ' 77'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 391-3916
publication_identifier:
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7021'
pubrep_id: '895'
quality_controlled: '1'
scopus_import: 1
status: public
title: Topological data analysis with Bregman divergences
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2017'
...
---
_id: '701'
abstract:
- lang: eng
text: A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if
it can be tiled by k simplices with disjoint interiors that are all mutually congruent
and similar to S. For d = 2, triangular k-reptiles exist for all k of the form
a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris,
and Williams. On the other hand, the only k-reptile simplices that are known for
d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify
the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra
can exist only for k = m^3. We then prove a weaker analogue of this result for
d = 4 by showing that four-dimensional k-reptile simplices can exist only for
k = m^2.
author:
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
- first_name: Zuzana
full_name: Patakova, Zuzana
id: 48B57058-F248-11E8-B48F-1D18A9856A87
last_name: Patakova
orcid: 0000-0002-3975-1683
citation:
ama: Kynčl J, Patakova Z. On the nonexistence of k reptile simplices in ℝ^3 and
ℝ^4. The Electronic Journal of Combinatorics. 2017;24(3):1-44.
apa: Kynčl, J., & Patakova, Z. (2017). On the nonexistence of k reptile simplices
in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. International
Press.
chicago: Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices
in ℝ^3 and ℝ^4.” The Electronic Journal of Combinatorics. International
Press, 2017.
ieee: J. Kynčl and Z. Patakova, “On the nonexistence of k reptile simplices in ℝ^3
and ℝ^4,” The Electronic Journal of Combinatorics, vol. 24, no. 3. International
Press, pp. 1–44, 2017.
ista: Kynčl J, Patakova Z. 2017. On the nonexistence of k reptile simplices in ℝ^3
and ℝ^4. The Electronic Journal of Combinatorics. 24(3), 1–44.
mla: Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices
in ℝ^3 and ℝ^4.” The Electronic Journal of Combinatorics, vol. 24, no.
3, International Press, 2017, pp. 1–44.
short: J. Kynčl, Z. Patakova, The Electronic Journal of Combinatorics 24 (2017)
1–44.
date_created: 2018-12-11T11:48:00Z
date_published: 2017-07-14T00:00:00Z
date_updated: 2021-01-12T08:11:28Z
day: '14'
ddc:
- '500'
department:
- _id: UlWa
file:
- access_level: open_access
checksum: a431e573e31df13bc0f66de3061006ec
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:25Z
date_updated: 2020-07-14T12:47:47Z
file_id: '5077'
file_name: IST-2018-984-v1+1_Patakova_on_the_nonexistence_of_k-reptile_simplices_in_R_3_and_R_4_2017.pdf
file_size: 544042
relation: main_file
file_date_updated: 2020-07-14T12:47:47Z
has_accepted_license: '1'
intvolume: ' 24'
issue: '3'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 1-44
publication: The Electronic Journal of Combinatorics
publication_identifier:
issn:
- '10778926'
publication_status: published
publisher: International Press
publist_id: '6996'
pubrep_id: '984'
quality_controlled: '1'
status: public
title: On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2017'
...
---
_id: '534'
abstract:
- lang: eng
text: We investigate the complexity of finding an embedded non-orientable surface
of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural
question in low-dimensional topology, and as a first non-trivial instance of embeddability
of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding
to the relatively few hardness results that are currently known in 3-manifold
topology. In addition, we show that the problem lies in NP when the Euler genus
g is odd, and we give an explicit algorithm in this case.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Benjamin
full_name: Burton, Benjamin
last_name: Burton
- first_name: Arnaud N
full_name: De Mesmay, Arnaud N
id: 3DB2F25C-F248-11E8-B48F-1D18A9856A87
last_name: De Mesmay
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-Manifolds.
Discrete & Computational Geometry. 2017;58(4):871-888. doi:10.1007/s00454-017-9900-0
apa: Burton, B., de Mesmay, A. N., & Wagner, U. (2017). Finding non-orientable
surfaces in 3-Manifolds. Discrete & Computational Geometry. Springer.
https://doi.org/10.1007/s00454-017-9900-0
chicago: Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable
Surfaces in 3-Manifolds.” Discrete & Computational Geometry. Springer,
2017. https://doi.org/10.1007/s00454-017-9900-0.
ieee: B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces
in 3-Manifolds,” Discrete & Computational Geometry, vol. 58, no. 4.
Springer, pp. 871–888, 2017.
ista: Burton B, de Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in
3-Manifolds. Discrete & Computational Geometry. 58(4), 871–888.
mla: Burton, Benjamin, et al. “Finding Non-Orientable Surfaces in 3-Manifolds.”
Discrete & Computational Geometry, vol. 58, no. 4, Springer, 2017,
pp. 871–88, doi:10.1007/s00454-017-9900-0.
short: B. Burton, A.N. de Mesmay, U. Wagner, Discrete & Computational Geometry
58 (2017) 871–888.
date_created: 2018-12-11T11:47:01Z
date_published: 2017-06-09T00:00:00Z
date_updated: 2023-02-21T17:01:34Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/s00454-017-9900-0
external_id:
arxiv:
- '1602.07907'
intvolume: ' 58'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.07907
month: '06'
oa: 1
oa_version: Preprint
page: 871 - 888
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- '01795376'
publication_status: published
publisher: Springer
publist_id: '7283'
quality_controlled: '1'
related_material:
record:
- id: '1379'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Finding non-orientable surfaces in 3-Manifolds
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 58
year: '2017'
...
---
_id: '568'
abstract:
- lang: eng
text: 'We study robust properties of zero sets of continuous maps f: X → ℝn. Formally,
we analyze the family Z< r(f) := (g-1(0): ||g - f|| < r) of all zero sets
of all continuous maps g closer to f than r in the max-norm. All of these sets
are outside A := (x: |f(x)| ≥ r) and we claim that Z< r(f) is fully determined
by A and an element of a certain cohomotopy group which (by a recent result) is
computable whenever the dimension of X is at most 2n - 3. By considering all r
> 0 simultaneously, the pointed cohomotopy groups form a persistence module-a
structure leading to persistence diagrams as in the case of persistent homology
or well groups. Eventually, we get a descriptor of persistent robust properties
of zero sets that has better descriptive power (Theorem A) and better computability
status (Theorem B) than the established well diagrams. Moreover, if we endow every
point of each zero set with gradients of the perturbation, the robust description
of the zero sets by elements of cohomotopy groups is in some sense the best possible
(Theorem C).'
author:
- first_name: Peter
full_name: Franek, Peter
id: 473294AE-F248-11E8-B48F-1D18A9856A87
last_name: Franek
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
citation:
ama: Franek P, Krcál M. Persistence of zero sets. Homology, Homotopy and Applications.
2017;19(2):313-342. doi:10.4310/HHA.2017.v19.n2.a16
apa: Franek, P., & Krcál, M. (2017). Persistence of zero sets. Homology,
Homotopy and Applications. International Press. https://doi.org/10.4310/HHA.2017.v19.n2.a16
chicago: Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” Homology,
Homotopy and Applications. International Press, 2017. https://doi.org/10.4310/HHA.2017.v19.n2.a16.
ieee: P. Franek and M. Krcál, “Persistence of zero sets,” Homology, Homotopy
and Applications, vol. 19, no. 2. International Press, pp. 313–342, 2017.
ista: Franek P, Krcál M. 2017. Persistence of zero sets. Homology, Homotopy and
Applications. 19(2), 313–342.
mla: Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” Homology, Homotopy
and Applications, vol. 19, no. 2, International Press, 2017, pp. 313–42, doi:10.4310/HHA.2017.v19.n2.a16.
short: P. Franek, M. Krcál, Homology, Homotopy and Applications 19 (2017) 313–342.
date_created: 2018-12-11T11:47:14Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:03:12Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.4310/HHA.2017.v19.n2.a16
ec_funded: 1
intvolume: ' 19'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1507.04310
month: '01'
oa: 1
oa_version: Submitted Version
page: 313 - 342
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 2590DB08-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '701309'
name: Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes
(H2020)
publication: Homology, Homotopy and Applications
publication_identifier:
issn:
- '15320073'
publication_status: published
publisher: International Press
publist_id: '7246'
quality_controlled: '1'
scopus_import: 1
status: public
title: Persistence of zero sets
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 19
year: '2017'
...
---
_id: '610'
abstract:
- lang: eng
text: 'The fact that the complete graph K5 does not embed in the plane has been
generalized in two independent directions. On the one hand, the solution of the
classical Heawood problem for graphs on surfaces established that the complete
graph Kn embeds in a closed surface M (other than the Klein bottle) if and only
if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-Betti number of M. On the
other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional
simplex (the higher-dimensional analogue of Kn+1) embeds in R2k if and only if
n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex
embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk
only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1
2k+1)bk. This is a common generalization of the case of graphs on surfaces as
well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we
prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold
with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than
the generalized Heawood inequality, but does not require the assumption that M
is (k−1)-connected. Our results generalize to maps without q-covered points, in
the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result
of Volovikov about maps that satisfy a certain homological triviality condition.'
acknowledgement: The work by Z. P. was partially supported by the Israel Science Foundation
grant ISF-768/12. The work by Z. P. and M. T. was partially supported by the project
CE-ITI (GACR P202/12/G061) of the Czech Science Foundation and by the ERC Advanced
Grant No. 267165. Part of the research work of M.T. was conducted at IST Austria,
supported by an IST Fellowship. The research of P. P. was supported by the ERC Advanced
grant no. 320924. The work by I. M. and U. W. was supported by the Swiss National
Science Foundation (grants SNSF-200020-138230 and SNSF-PP00P2-138948). The collaboration
between U. W. and X. G. was partially supported by the LabEx Bézout (ANR-10-LABX-58).
author:
- first_name: Xavier
full_name: Goaoc, Xavier
last_name: Goaoc
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
- 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, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized
Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability
result. Israel Journal of Mathematics. 2017;222(2):841-866. doi:10.1007/s11856-017-1607-7'
apa: 'Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., & Wagner,
U. (2017). On generalized Heawood inequalities for manifolds: A van Kampen–Flores
type nonembeddability result. Israel Journal of Mathematics. Springer.
https://doi.org/10.1007/s11856-017-1607-7'
chicago: 'Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer,
and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores
Type Nonembeddability Result.” Israel Journal of Mathematics. Springer,
2017. https://doi.org/10.1007/s11856-017-1607-7.'
ieee: 'X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner,
“On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability
result,” Israel Journal of Mathematics, vol. 222, no. 2. Springer, pp.
841–866, 2017.'
ista: 'Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2017. On generalized
Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability
result. Israel Journal of Mathematics. 222(2), 841–866.'
mla: 'Goaoc, Xavier, et al. “On Generalized Heawood Inequalities for Manifolds:
A van Kampen–Flores Type Nonembeddability Result.” Israel Journal of Mathematics,
vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:10.1007/s11856-017-1607-7.'
short: X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, Israel
Journal of Mathematics 222 (2017) 841–866.
date_created: 2018-12-11T11:47:29Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2023-02-23T10:02:13Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s11856-017-1607-7
ec_funded: 1
intvolume: ' 222'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1610.09063
month: '10'
oa: 1
oa_version: Preprint
page: 841 - 866
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Israel Journal of Mathematics
publication_status: published
publisher: Springer
publist_id: '7194'
quality_controlled: '1'
related_material:
record:
- id: '1511'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: 'On generalized Heawood inequalities for manifolds: A van Kampen–Flores type
nonembeddability result'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 222
year: '2017'
...
---
_id: '6517'
abstract:
- lang: eng
text: A (possibly degenerate) drawing of a graph G in the plane is approximable
by an embedding if it can be turned into an embedding by an arbitrarily small
perturbation. We show that testing, whether a drawing of a planar graph G in the
plane is approximable by an embedding, can be carried out in polynomial time,
if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation
system (or equivalently the faces) of the embedding of G and the choice of outer
face are fixed. In other words, we show that c-planarity with embedded pipes is
tractable for graphs with fixed embeddings. To the best of our knowledge an analogous
result was previously known essentially only when G is a cycle.
article_number: '34'
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ISAAC.2017.34'
apa: 'Fulek, R. (2017). Embedding graphs into embedded graphs (Vol. 92). Presented
at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ISAAC.2017.34'
chicago: Fulek, Radoslav. “Embedding Graphs into Embedded Graphs,” Vol. 92. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ISAAC.2017.34.
ieee: 'R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC:
International Symposium on Algorithms and Computation, Phuket, Thailand, 2017,
vol. 92.'
ista: 'Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International
Symposium on Algorithms and Computation vol. 92, 34.'
mla: Fulek, Radoslav. Embedding Graphs into Embedded Graphs. Vol. 92, 34,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ISAAC.2017.34.
short: R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-12-22
location: Phuket, Thailand
name: 'ISAAC: International Symposium on Algorithms and Computation'
start_date: 2017-12-09
date_created: 2019-06-04T12:11:52Z
date_published: 2017-12-01T00:00:00Z
date_updated: 2021-01-12T08:07:51Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.ISAAC.2017.34
ec_funded: 1
file:
- access_level: open_access
checksum: fc7a643e29621c8bbe49d36b39081f31
content_type: application/pdf
creator: kschuh
date_created: 2019-06-04T12:20:35Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6518'
file_name: 2017_LIPIcs-Fulek.pdf
file_size: 588982
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 92'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Embedding graphs into embedded 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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 92
year: '2017'
...
---
_id: '424'
abstract:
- lang: eng
text: 'We show that very weak topological assumptions are enough to ensure the existence
of a Helly-type theorem. More precisely, we show that for any non-negative integers
b and d there exists an integer h(b, d) such that the following holds. If F is
a finite family of subsets of Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤
i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced
Z2-Betti numbers (with singular homology). These topological conditions are sharp:
not controlling any of these [d/2] first Betti numbers allow for families with
unbounded Helly number. Our proofs combine homological non-embeddability results
with a Ramsey-based approach to build, given an arbitrary simplicial complex K,
some well-behaved chain map C*(K)→C*(Rd).'
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
last_name: Patakova
orcid: 0000-0002-3975-1683
- first_name: Martin
full_name: Tancer, Martin
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. Bounding helly numbers via
betti numbers. In: Loebl M, Nešetřil J, Thomas R, eds. A Journey through Discrete
Mathematics: A Tribute to Jiri Matousek. A Journey Through Discrete Mathematics.
Springer; 2017:407-447. doi:10.1007/978-3-319-44479-6_17'
apa: 'Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2017). Bounding
helly numbers via betti numbers. In M. Loebl, J. Nešetřil, & R. Thomas (Eds.),
A Journey through Discrete Mathematics: A Tribute to Jiri Matousek (pp.
407–447). Springer. https://doi.org/10.1007/978-3-319-44479-6_17'
chicago: 'Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner.
“Bounding Helly Numbers via Betti Numbers.” In A Journey through Discrete Mathematics:
A Tribute to Jiri Matousek, edited by Martin Loebl, Jaroslav Nešetřil, and
Robin Thomas, 407–47. A Journey Through Discrete Mathematics. Springer, 2017.
https://doi.org/10.1007/978-3-319-44479-6_17.'
ieee: 'X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding helly
numbers via betti numbers,” in A Journey through Discrete Mathematics: A Tribute
to Jiri Matousek, M. Loebl, J. Nešetřil, and R. Thomas, Eds. Springer, 2017,
pp. 407–447.'
ista: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2017.Bounding helly numbers
via betti numbers. In: A Journey through Discrete Mathematics: A Tribute to Jiri
Matousek. , 407–447.'
mla: 'Goaoc, Xavier, et al. “Bounding Helly Numbers via Betti Numbers.” A Journey
through Discrete Mathematics: A Tribute to Jiri Matousek, edited by Martin
Loebl et al., Springer, 2017, pp. 407–47, doi:10.1007/978-3-319-44479-6_17.'
short: 'X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, M. Loebl, J.
Nešetřil, R. Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute
to Jiri Matousek, Springer, 2017, pp. 407–447.'
date_created: 2018-12-11T11:46:24Z
date_published: 2017-10-06T00:00:00Z
date_updated: 2024-02-28T12:59:37Z
day: '06'
department:
- _id: UlWa
doi: 10.1007/978-3-319-44479-6_17
editor:
- first_name: Martin
full_name: Loebl, Martin
last_name: Loebl
- first_name: Jaroslav
full_name: Nešetřil, Jaroslav
last_name: Nešetřil
- first_name: Robin
full_name: Thomas, Robin
last_name: Thomas
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1310.4613v3
month: '10'
oa: 1
oa_version: Published Version
page: 407 - 447
publication: 'A Journey through Discrete Mathematics: A Tribute to Jiri Matousek'
publication_identifier:
isbn:
- 978-331944479-6
publication_status: published
publisher: Springer
publist_id: '7399'
quality_controlled: '1'
related_material:
record:
- id: '1512'
relation: earlier_version
status: public
scopus_import: 1
series_title: A Journey Through Discrete Mathematics
status: public
title: Bounding helly numbers via betti numbers
type: book_chapter
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '1123'
abstract:
- lang: eng
text: "Motivated by topological Tverberg-type problems in topological combinatorics
and by classical\r\nresults about embeddings (maps without double points), we
study the question whether a finite\r\nsimplicial complex K can be mapped into
Rd without triple, quadruple, or, more generally, r-fold points (image points
with at least r distinct preimages), for a given multiplicity r ≤ 2. In particular,
we are interested in maps f : K → Rd that have no global r -fold intersection
points, i.e., no r -fold points with preimages in r pairwise disjoint simplices
of K , and we seek necessary and sufficient conditions for the existence of such
maps.\r\n\r\nWe present higher-multiplicity analogues of several classical results
for embeddings, in particular of the completeness of the Van Kampen obstruction
\ for embeddability of k -dimensional\r\ncomplexes into R2k , k ≥ 3. Speciffically,
we show that under suitable restrictions on the dimensions(viz., if dimK = (r
≥ 1)k and d = rk \\ for some k ≥ 3), a well-known deleted product criterion
(DPC ) is not only necessary but also sufficient for the existence of maps without
global r -fold points. Our main technical tool is a higher-multiplicity version
of the classical Whitney trick , by which pairs of isolated r -fold points of
opposite sign can be eliminated by local modiffications of the map, assuming
codimension d – dimK ≥ 3.\r\n\r\nAn important guiding idea for our work was that
suffciency of the DPC, together with an old\r\nresult of Özaydin's on the existence
of equivariant maps, might yield an approach to disproving the remaining open
cases of the the long-standing topological Tverberg conjecture , i.e., to construct
maps from the N -simplex σN to Rd without r-Tverberg points when r not a prime
power and\r\nN = (d + 1)(r – 1). Unfortunately, our proof of the sufficiency
of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K =
σN .\r\n\r\nIn 2015, Frick [16] found a very elegant way to overcome this \\codimension
3 obstacle" and\r\nto construct the first counterexamples to the topological
Tverberg conjecture for all parameters(d; r ) with d ≥ 3r + 1 and r not a prime
power, by a reduction1 to a suitable lower-dimensional skeleton, for which the
codimension 3 restriction is satisfied and maps without r -Tverberg points exist
by Özaydin's result and sufficiency of the DPC.\r\n\r\nIn this thesis, we present
a different construction (which does not use the constraint method) that yields
counterexamples for d ≥ 3r , r not a prime power. "
acknowledgement: "Foremost, I would like to thank Uli Wagner for introducing me to
the exciting interface between\r\ntopology and combinatorics, and for our subsequent
years of fruitful collaboration.\r\nIn our creative endeavors to eliminate intersection
points, we had the chance to be joined later\r\nby Sergey Avvakumov and Arkadiy
Skopenkov, which led us to new surprises in dimension 12.\r\nMy stay at EPFL and
IST Austria was made very agreeable thanks to all these wonderful\r\npeople: Cyril
Becker, Marek Filakovsky, Peter Franek, Radoslav Fulek, Peter Gazi, Kristof Huszar,\r\nMarek
Krcal, Zuzana Masarova, Arnaud de Mesmay, Filip Moric, Michal Rybar, Martin Tancer,\r\nand
Stephan Zhechev.\r\nFinally, I would like to thank my thesis committee Herbert Edelsbrunner
and Roman Karasev\r\nfor their careful reading of the present manuscript and for
the many improvements they suggested."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
citation:
ama: 'Mabillard I. Eliminating higher-multiplicity intersections: an r-fold Whitney
trick for the topological Tverberg conjecture. 2016.'
apa: 'Mabillard, I. (2016). Eliminating higher-multiplicity intersections: an
r-fold Whitney trick for the topological Tverberg conjecture. Institute of
Science and Technology Austria.'
chicago: 'Mabillard, Isaac. “Eliminating Higher-Multiplicity Intersections: An r-Fold
Whitney Trick for the Topological Tverberg Conjecture.” Institute of Science and
Technology Austria, 2016.'
ieee: 'I. Mabillard, “Eliminating higher-multiplicity intersections: an r-fold Whitney
trick for the topological Tverberg conjecture,” Institute of Science and Technology
Austria, 2016.'
ista: 'Mabillard I. 2016. Eliminating higher-multiplicity intersections: an r-fold
Whitney trick for the topological Tverberg conjecture. Institute of Science and
Technology Austria.'
mla: 'Mabillard, Isaac. Eliminating Higher-Multiplicity Intersections: An r-Fold
Whitney Trick for the Topological Tverberg Conjecture. Institute of Science
and Technology Austria, 2016.'
short: 'I. Mabillard, Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney
Trick for the Topological Tverberg Conjecture, Institute of Science and Technology
Austria, 2016.'
date_created: 2018-12-11T11:50:16Z
date_published: 2016-08-01T00:00:00Z
date_updated: 2023-09-07T11:56:28Z
day: '01'
ddc:
- '500'
degree_awarded: PhD
department:
- _id: UlWa
file:
- access_level: closed
checksum: 2d140cc924cd1b764544906fc22684ef
content_type: application/pdf
creator: dernst
date_created: 2019-08-13T08:45:27Z
date_updated: 2019-08-13T08:45:27Z
file_id: '6809'
file_name: Thesis_final version_Mabillard_w_signature_page.pdf
file_size: 2227916
relation: main_file
- access_level: open_access
checksum: 2d140cc924cd1b764544906fc22684ef
content_type: application/pdf
creator: dernst
date_created: 2021-02-22T11:36:34Z
date_updated: 2021-02-22T11:36:34Z
file_id: '9178'
file_name: 2016_Mabillard_Thesis.pdf
file_size: 2227916
relation: main_file
success: 1
file_date_updated: 2021-02-22T11:36:34Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '55'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6237'
related_material:
record:
- id: '2159'
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: 'Eliminating higher-multiplicity intersections: an r-fold Whitney trick for
the topological Tverberg conjecture'
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2016'
...
---
_id: '1164'
abstract:
- lang: eng
text: 'A drawing of a graph G is radial if the vertices of G are placed on concentric
circles C1, … , Ck with common center c, and edges are drawn radially: every edge
intersects every circle centered at c at most once. G is radial planar if it has
a radial embedding, that is, a crossing-free radial drawing. If the vertices of
G are ordered or partitioned into ordered levels (as they are for leveled graphs),
we require that the assignment of vertices to circles corresponds to the given
ordering or leveling. A pair of edges e and f in a graph is independent if e and
f do not share a vertex. We show that a graph G is radial planar if G has a radial
drawing in which every two independent edges cross an even number of times; the
radial embedding has the same leveling as the radial drawing. In other words,
we establish the strong Hanani-Tutte theorem for radial planarity. This characterization
yields a very simple algorithm for radial planarity testing.'
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: Michael
full_name: Pelsmajer, Michael
last_name: Pelsmajer
- first_name: Marcus
full_name: Schaefer, Marcus
last_name: Schaefer
citation:
ama: 'Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity II. In:
Vol 9801. Springer; 2016:468-481. doi:10.1007/978-3-319-50106-2_36'
apa: 'Fulek, R., Pelsmajer, M., & Schaefer, M. (2016). Hanani-Tutte for radial
planarity II (Vol. 9801, pp. 468–481). Presented at the GD: Graph Drawing and
Network Visualization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_36'
chicago: Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte
for Radial Planarity II,” 9801:468–81. Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_36.
ieee: 'R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity
II,” presented at the GD: Graph Drawing and Network Visualization, Athens, Greece,
2016, vol. 9801, pp. 468–481.'
ista: 'Fulek R, Pelsmajer M, Schaefer M. 2016. Hanani-Tutte for radial planarity
II. GD: Graph Drawing and Network Visualization, LNCS, vol. 9801, 468–481.'
mla: Fulek, Radoslav, et al. Hanani-Tutte for Radial Planarity II. Vol. 9801,
Springer, 2016, pp. 468–81, doi:10.1007/978-3-319-50106-2_36.
short: R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2016, pp. 468–481.
conference:
end_date: 2016-09-21
location: Athens, Greece
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2016-09-19
date_created: 2018-12-11T11:50:29Z
date_published: 2016-12-08T00:00:00Z
date_updated: 2023-02-23T10:05:57Z
day: '08'
department:
- _id: UlWa
doi: 10.1007/978-3-319-50106-2_36
ec_funded: 1
external_id:
arxiv:
- '1608.08662'
intvolume: ' 9801'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1608.08662
month: '12'
oa: 1
oa_version: Preprint
page: 468 - 481
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '6193'
quality_controlled: '1'
related_material:
record:
- id: '1113'
relation: later_version
status: public
- id: '1595'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Hanani-Tutte for radial planarity II
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9801
year: '2016'
...
---
_id: '1165'
abstract:
- lang: eng
text: We show that c-planarity is solvable in quadratic time for flat clustered
graphs with three clusters if the combinatorial embedding of the underlying graph
is fixed. In simpler graph-theoretical terms our result can be viewed as follows.
Given a graph G with the vertex set partitioned into three parts embedded on a
2-sphere, our algorithm decides if we can augment G by adding edges without creating
an edge-crossing so that in the resulting spherical graph the vertices of each
part induce a connected sub-graph. We proceed by a reduction to the problem of
testing the existence of a perfect matching in planar bipartite graphs. We formulate
our result in a slightly more general setting of cyclic clustered graphs, i.e.,
the simple graph obtained by contracting each cluster, where we disregard loops
and multi-edges, is a cycle.
acknowledgement: "R. Fulek—The research leading to these results has received funding
from the People Programme (Marie Curie Actions) of the European Union’s Seventh
Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].\r\nI
would like to thank Jan Kynčl and Dömötör Pálvölgyi for many comments and suggestions
that helped to improve the presentation of the result."
alternative_title:
- LNCS
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. C-planarity of embedded cyclic c-graphs. In: Vol 9801. Springer;
2016:94-106. doi:10.1007/978-3-319-50106-2_8'
apa: 'Fulek, R. (2016). C-planarity of embedded cyclic c-graphs (Vol. 9801, pp.
94–106). Presented at the GD: Graph Drawing and Network Visualization, Athens,
Greece: Springer. https://doi.org/10.1007/978-3-319-50106-2_8'
chicago: Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs,” 9801:94–106.
Springer, 2016. https://doi.org/10.1007/978-3-319-50106-2_8.
ieee: 'R. Fulek, “C-planarity of embedded cyclic c-graphs,” presented at the GD:
Graph Drawing and Network Visualization, Athens, Greece, 2016, vol. 9801, pp.
94–106.'
ista: 'Fulek R. 2016. C-planarity of embedded cyclic c-graphs. GD: Graph Drawing
and Network Visualization, LNCS, vol. 9801, 94–106.'
mla: Fulek, Radoslav. C-Planarity of Embedded Cyclic c-Graphs. Vol. 9801,
Springer, 2016, pp. 94–106, doi:10.1007/978-3-319-50106-2_8.
short: R. Fulek, in:, Springer, 2016, pp. 94–106.
conference:
end_date: 2016-09-21
location: Athens, Greece
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2016-09-19
date_created: 2018-12-11T11:50:30Z
date_published: 2016-12-08T00:00:00Z
date_updated: 2023-09-27T12:14:48Z
day: '08'
department:
- _id: UlWa
doi: 10.1007/978-3-319-50106-2_8
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.01346
month: '12'
oa: 1
oa_version: Preprint
page: 94 - 106
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '6192'
quality_controlled: '1'
related_material:
record:
- id: '794'
relation: later_version
status: public
scopus_import: 1
status: public
title: C-planarity of embedded cyclic c-graphs
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: '9801 '
year: '2016'
...
---
_id: '1522'
abstract:
- lang: eng
text: 'We classify smooth Brunnian (i.e., unknotted on both components) embeddings
(S2 × S1) ⊔ S3 → ℝ6. Any Brunnian embedding (S2 × S1) ⊔ S3 → ℝ6 is isotopic to
an explicitly constructed embedding fk,m,n for some integers k, m, n such that
m ≡ n (mod 2). Two embeddings fk,m,n and fk′ ,m′,n′ are isotopic if and only if
k = k′, m ≡ m′ (mod 2k) and n ≡ n′ (mod 2k). We use Haefliger’s classification
of embeddings S3 ⊔ S3 → ℝ6 in our proof. The relation between the embeddings (S2
× S1) ⊔ S3 → ℝ6 and S3 ⊔ S3 → ℝ6 is not trivial, however. For example, we show
that there exist embeddings f: (S2 ×S1) ⊔ S3 → ℝ6 and g, g′ : S3 ⊔ S3 → ℝ6 such
that the componentwise embedded connected sum f # g is isotopic to f # g′ but
g is not isotopic to g′.'
acknowledgement: "I thank A. Skopenkov for telling me about the problem and for his
useful remarks. I also thank A. Sossinsky,\r\nA. Zhubr, M. Skopenkov, P. Akhmetiev,
and an anonymous referee for their feedback. Author was partially\r\nsupported
by Dobrushin fellowship, 2013, and by RFBR grant 15-01-06302."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Serhii
full_name: Avvakumov, Serhii
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
citation:
ama: Avvakumov S. The classification of certain linked 3-manifolds in 6-space. Moscow
Mathematical Journal. 2016;16(1):1-25. doi:10.17323/1609-4514-2016-16-1-1-25
apa: Avvakumov, S. (2016). The classification of certain linked 3-manifolds in 6-space.
Moscow Mathematical Journal. Independent University of Moscow. https://doi.org/10.17323/1609-4514-2016-16-1-1-25
chicago: Avvakumov, Sergey. “The Classification of Certain Linked 3-Manifolds in
6-Space.” Moscow Mathematical Journal. Independent University of Moscow,
2016. https://doi.org/10.17323/1609-4514-2016-16-1-1-25.
ieee: S. Avvakumov, “The classification of certain linked 3-manifolds in 6-space,”
Moscow Mathematical Journal, vol. 16, no. 1. Independent University of
Moscow, pp. 1–25, 2016.
ista: Avvakumov S. 2016. The classification of certain linked 3-manifolds in 6-space.
Moscow Mathematical Journal. 16(1), 1–25.
mla: Avvakumov, Sergey. “The Classification of Certain Linked 3-Manifolds in 6-Space.”
Moscow Mathematical Journal, vol. 16, no. 1, Independent University of
Moscow, 2016, pp. 1–25, doi:10.17323/1609-4514-2016-16-1-1-25.
short: S. Avvakumov, Moscow Mathematical Journal 16 (2016) 1–25.
date_created: 2018-12-11T11:52:30Z
date_published: 2016-01-01T00:00:00Z
date_updated: 2022-02-25T10:15:57Z
day: '01'
department:
- _id: UlWa
doi: 10.17323/1609-4514-2016-16-1-1-25
external_id:
arxiv:
- '1408.3918'
intvolume: ' 16'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1408.3918
month: '01'
oa: 1
oa_version: Preprint
page: 1 - 25
publication: Moscow Mathematical Journal
publication_identifier:
eissn:
- 1609-4514
publication_status: published
publisher: Independent University of Moscow
publist_id: '5652'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The classification of certain linked 3-manifolds in 6-space
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2016'
...
---
_id: '1523'
abstract:
- lang: eng
text: For random graphs, the containment problem considers the probability that
a binomial random graph G(n, p) contains a given graph as a substructure. When
asking for the graph as a topological minor, i.e., for a copy of a subdivision
of the given graph, it is well known that the (sharp) threshold is at p = 1/n.
We consider a natural analogue of this question for higher-dimensional random
complexes Xk(n, p), first studied by Cohen, Costa, Farber and Kappeler for k =
2. Improving previous results, we show that p = Θ(1/ √n) is the (coarse) threshold
for containing a subdivision of any fixed complete 2-complex. For higher dimensions
k > 2, we get that p = O(n−1/k) is an upper bound for the threshold probability
of containing a subdivision of a fixed k-dimensional complex.
acknowledgement: This research was supported by the Swiss National Science Foundation
(SNF Projects 200021-125309 and 200020-138230
author:
- first_name: Anna
full_name: Gundert, Anna
last_name: Gundert
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Gundert A, Wagner U. On topological minors in random simplicial complexes.
Proceedings of the American Mathematical Society. 2016;144(4):1815-1828.
doi:10.1090/proc/12824
apa: Gundert, A., & Wagner, U. (2016). On topological minors in random simplicial
complexes. Proceedings of the American Mathematical Society. American Mathematical
Society. https://doi.org/10.1090/proc/12824
chicago: Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial
Complexes.” Proceedings of the American Mathematical Society. American
Mathematical Society, 2016. https://doi.org/10.1090/proc/12824.
ieee: A. Gundert and U. Wagner, “On topological minors in random simplicial complexes,”
Proceedings of the American Mathematical Society, vol. 144, no. 4. American
Mathematical Society, pp. 1815–1828, 2016.
ista: Gundert A, Wagner U. 2016. On topological minors in random simplicial complexes.
Proceedings of the American Mathematical Society. 144(4), 1815–1828.
mla: Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial
Complexes.” Proceedings of the American Mathematical Society, vol. 144,
no. 4, American Mathematical Society, 2016, pp. 1815–28, doi:10.1090/proc/12824.
short: A. Gundert, U. Wagner, Proceedings of the American Mathematical Society 144
(2016) 1815–1828.
date_created: 2018-12-11T11:52:30Z
date_published: 2016-04-01T00:00:00Z
date_updated: 2021-01-12T06:51:22Z
day: '01'
department:
- _id: UlWa
doi: 10.1090/proc/12824
intvolume: ' 144'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1404.2106
month: '04'
oa: 1
oa_version: Preprint
page: 1815 - 1828
publication: Proceedings of the American Mathematical Society
publication_status: published
publisher: American Mathematical Society
publist_id: '5650'
quality_controlled: '1'
scopus_import: 1
status: public
title: On topological minors in random simplicial complexes
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 144
year: '2016'
...
---
_id: '1348'
abstract:
- lang: eng
text: 'A drawing in the plane (ℝ2) of a graph G = (V,E) equipped with a function
γ : V → ℕ is x-bounded if (i) x(u) < x(v) whenever γ(u) < γ(v) and (ii)
γ(u) ≤ γ(w) ≤ γ(v), where uv ∈ E and γ(u) ≤ γ(v), whenever x(w) ∈ x(uv), where
x(.) denotes the projection to the xaxis.We prove a characterization of isotopy
classes of embeddings of connected graphs equipped with γ in the plane containing
an x-bounded embedding.Then we present an efficient algorithm, which relies on
our result, for testing the existence of an x-bounded embedding if the given graph
is a forest.This partially answers a question raised recently by Angelini et al.and
Chang et al., and proves that c-planarity testing of flat clustered graphs with
three clusters is tractable when the underlying abstract graph is a forest.'
alternative_title:
- LNCS
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
citation:
ama: 'Fulek R. Bounded embeddings of graphs in the plane. In: Vol 9843. Springer;
2016:31-42. doi:10.1007/978-3-319-44543-4_3'
apa: 'Fulek, R. (2016). Bounded embeddings of graphs in the plane (Vol. 9843, pp.
31–42). Presented at the IWOCA: International Workshop on Combinatorial Algorithms,
Helsinki, Finland: Springer. https://doi.org/10.1007/978-3-319-44543-4_3'
chicago: Fulek, Radoslav. “Bounded Embeddings of Graphs in the Plane,” 9843:31–42.
Springer, 2016. https://doi.org/10.1007/978-3-319-44543-4_3.
ieee: 'R. Fulek, “Bounded embeddings of graphs in the plane,” presented at the IWOCA:
International Workshop on Combinatorial Algorithms, Helsinki, Finland, 2016, vol.
9843, pp. 31–42.'
ista: 'Fulek R. 2016. Bounded embeddings of graphs in the plane. IWOCA: International
Workshop on Combinatorial Algorithms, LNCS, vol. 9843, 31–42.'
mla: Fulek, Radoslav. Bounded Embeddings of Graphs in the Plane. Vol. 9843,
Springer, 2016, pp. 31–42, doi:10.1007/978-3-319-44543-4_3.
short: R. Fulek, in:, Springer, 2016, pp. 31–42.
conference:
end_date: 2018-08-19
location: Helsinki, Finland
name: 'IWOCA: International Workshop on Combinatorial Algorithms'
start_date: 2016-08-17
date_created: 2018-12-11T11:51:31Z
date_published: 2016-08-09T00:00:00Z
date_updated: 2021-01-12T06:50:03Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/978-3-319-44543-4_3
ec_funded: 1
intvolume: ' 9843'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1610.07144
month: '08'
oa: 1
oa_version: Preprint
page: 31 - 42
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '5901'
quality_controlled: '1'
scopus_import: 1
status: public
title: Bounded embeddings of graphs in the plane
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9843
year: '2016'
...
---
_id: '1378'
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 X → ℝd there exists a point
p ∈ ℝd whose preimage intersects a positive fraction μ > 0 of the d-cells of
X. More generally, the conclusion holds if ℝd is replaced by any d-dimensional
piecewise-linear (PL) manifold M, with a constant μ that depends only on d and
on the expansion properties of X, but not on M.'
alternative_title:
- LIPIcs
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. In:
Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing;
2016:35.1-35.10. doi:10.4230/LIPIcs.SoCG.2016.35'
apa: 'Dotterrer, D., Kaufman, T., & Wagner, U. (2016). On expansion and topological
overlap (Vol. 51, p. 35.1-35.10). Presented at the SoCG: Symposium on Computational
Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH,
Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2016.35'
chicago: Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological
Overlap,” 51:35.1-35.10. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH,
Dagstuhl Publishing, 2016. https://doi.org/10.4230/LIPIcs.SoCG.2016.35.
ieee: 'D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,”
presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA,
2016, vol. 51, p. 35.1-35.10.'
ista: 'Dotterrer D, Kaufman T, Wagner U. 2016. On expansion and topological overlap.
SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 35.1-35.10.'
mla: Dotterrer, Dominic, et al. On Expansion and Topological Overlap. Vol.
51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing,
2016, p. 35.1-35.10, doi:10.4230/LIPIcs.SoCG.2016.35.
short: D. Dotterrer, T. Kaufman, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum
fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10.
conference:
end_date: 2016-06-17
location: Medford, MA, USA
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2016-06-14
date_created: 2018-12-11T11:51:41Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2023-09-27T12:29:56Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2016.35
file:
- access_level: open_access
checksum: cee65b0e722d50f9d1cc70c90ec1d59b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:38Z
date_updated: 2020-07-14T12:44:47Z
file_id: '4699'
file_name: IST-2016-623-v1+1_LIPIcs-SoCG-2016-35.pdf
file_size: 536923
relation: main_file
file_date_updated: 2020-07-14T12:44:47Z
has_accepted_license: '1'
intvolume: ' 51'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 35.1 - 35.10
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication_status: published
publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
publist_id: '5833'
pubrep_id: '623'
quality_controlled: '1'
related_material:
record:
- id: '742'
relation: later_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: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 51
year: '2016'
...
---
_id: '1379'
abstract:
- lang: eng
text: We investigate the complexity of finding an embedded non-orientable surface
of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural
question in low-dimensional topology, and as a first non-trivial instance of embeddability
of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding
to the relatively few hardness results that are currently known in 3-manifold
topology. In addition, we show that the problem lies in NP when the Euler genus
g is odd, and we give an explicit algorithm in this case.
alternative_title:
- LIPIcs
author:
- first_name: Benjamin
full_name: Burton, Benjamin
last_name: Burton
- first_name: Arnaud N
full_name: De Mesmay, Arnaud N
id: 3DB2F25C-F248-11E8-B48F-1D18A9856A87
last_name: De Mesmay
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-manifolds.
In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing;
2016:24.1-24.15. doi:10.4230/LIPIcs.SoCG.2016.24'
apa: 'Burton, B., de Mesmay, A. N., & Wagner, U. (2016). Finding non-orientable
surfaces in 3-manifolds (Vol. 51, p. 24.1-24.15). Presented at the SoCG: Symposium
on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum
fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2016.24'
chicago: Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable
Surfaces in 3-Manifolds,” 51:24.1-24.15. Schloss Dagstuhl- Leibniz-Zentrum fur
Informatik GmbH, Dagstuhl Publishing, 2016. https://doi.org/10.4230/LIPIcs.SoCG.2016.24.
ieee: 'B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces
in 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Medford,
MA, USA, 2016, vol. 51, p. 24.1-24.15.'
ista: 'Burton B, de Mesmay AN, Wagner U. 2016. Finding non-orientable surfaces in
3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 24.1-24.15.'
mla: Burton, Benjamin, et al. Finding Non-Orientable Surfaces in 3-Manifolds.
Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing,
2016, p. 24.1-24.15, doi:10.4230/LIPIcs.SoCG.2016.24.
short: B. Burton, A.N. de Mesmay, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum
fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15.
conference:
end_date: 2016-06-17
location: Medford, MA, USA
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2016-06-14
date_created: 2018-12-11T11:51:41Z
date_published: 2016-06-01T00:00:00Z
date_updated: 2023-02-23T12:23:20Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2016.24
file:
- access_level: open_access
checksum: f04248a61c24297cfabd30c5f8e0deb9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:12Z
date_updated: 2020-07-14T12:44:47Z
file_id: '4930'
file_name: IST-2016-622-v1+1_LIPIcs-SoCG-2016-24.pdf
file_size: 574770
relation: main_file
file_date_updated: 2020-07-14T12:44:47Z
has_accepted_license: '1'
intvolume: ' 51'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 24.1 - 24.15
publication_status: published
publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
publist_id: '5832'
pubrep_id: '622'
quality_controlled: '1'
related_material:
record:
- id: '534'
relation: later_version
status: public
scopus_import: 1
status: public
title: Finding non-orientable surfaces in 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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 51
year: '2016'
...