---
_id: '14888'
abstract:
- lang: eng
text: 'A face in a curve arrangement is called popular if it is bounded by the same
curve multiple times. Motivated by the automatic generation of curved nonogram
puzzles, we investigate possibilities to eliminate the popular faces in an arrangement
by inserting a single additional curve. This turns out to be NP-hard; however,
it becomes tractable when the number of popular faces is small: We present a probabilistic
FPT-approach in the number of popular faces.'
acknowledgement: 'This work was initiated at the 16th European Research Week on Geometric
Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF):
W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035].
A preliminary version of this work has been presented at the 38th European Workshop
on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper,
which includes appendices but is otherwise identical, is available as a technical
report [10].'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Phoebe
full_name: De Nooijer, Phoebe
last_name: De Nooijer
- first_name: Soeren
full_name: Terziadis, Soeren
last_name: Terziadis
- first_name: Alexandra
full_name: Weinberger, Alexandra
last_name: Weinberger
- 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: Tamara
full_name: Mchedlidze, Tamara
last_name: Mchedlidze
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- first_name: Günter
full_name: Rote, Günter
last_name: Rote
citation:
ama: 'De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve
arrangements. In: 31st International Symposium on Graph Drawing and Network
Visualization. Vol 14466. Springer Nature; 2024:18-33. doi:10.1007/978-3-031-49275-4_2'
apa: 'De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T.,
Löffler, M., & Rote, G. (2024). Removing popular faces in curve arrangements.
In 31st International Symposium on Graph Drawing and Network Visualization
(Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature.
https://doi.org/10.1007/978-3-031-49275-4_2'
chicago: De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová,
Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve
Arrangements.” In 31st International Symposium on Graph Drawing and Network
Visualization, 14466:18–33. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49275-4_2.
ieee: P. De Nooijer et al., “Removing popular faces in curve arrangements,”
in 31st International Symposium on Graph Drawing and Network Visualization,
Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33.
ista: 'De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler
M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International
Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network
Visualization, LNCS, vol. 14466, 18–33.'
mla: De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.”
31st International Symposium on Graph Drawing and Network Visualization,
vol. 14466, Springer Nature, 2024, pp. 18–33, doi:10.1007/978-3-031-49275-4_2.
short: P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M.
Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network
Visualization, Springer Nature, 2024, pp. 18–33.
conference:
end_date: 2023-09-22
location: Isola delle Femmine, Palermo, Italy
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2023-09-20
date_created: 2024-01-28T23:01:43Z
date_published: 2024-01-06T00:00:00Z
date_updated: 2025-07-21T07:28:03Z
day: '06'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/978-3-031-49275-4_2
external_id:
arxiv:
- '2202.12175'
intvolume: ' 14466'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2202.12175
month: '01'
oa: 1
oa_version: Preprint
page: 18-33
project:
- _id: bdb2a702-d553-11ed-ba76-f12e3e5a3bc6
grant_number: '101087907'
name: 'A quantum hybrid of atoms and milligram-scale pendulums: towards gravitational
quantum mechanics'
publication: 31st International Symposium on Graph Drawing and Network Visualization
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031492747'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Removing popular faces in curve arrangements
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14466
year: '2024'
...
---
_id: '12833'
abstract:
- lang: eng
text: 'The input to the token swapping problem is a graph with vertices v1, v2,
. . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal
is to get token i to vertex vi for all i= 1, . . . , n using a minimum number
of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token
swapping on a tree, also known as “sorting with a transposition tree,” is not
known to be in P nor NP-complete. We present some partial results: 1. An optimum
swap sequence may need to perform a swap on a leaf vertex that has the correct
token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that
fixes happy leaves—as all known approximation algorithms for the problem do—has
approximation factor at least 4/3. Furthermore, the two best-known 2-approximation
algorithms have approximation factor exactly 2. 3. A generalized problem—weighted
coloured token swapping—is NP-complete on trees, but solvable in polynomial time
on paths and stars. In this version, tokens and vertices have colours, and colours
have weights. The goal is to get every token to a vertex of the same colour, and
the cost of a swap is the sum of the weights of the two tokens involved.'
acknowledgement: "This work was begun at the University of Waterloo and was partially
supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n"
article_number: '9'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ahmad
full_name: Biniaz, Ahmad
last_name: Biniaz
- first_name: Kshitij
full_name: Jain, Kshitij
last_name: Jain
- 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: Tillmann
full_name: Miltzow, Tillmann
last_name: Miltzow
- first_name: Debajyoti
full_name: Mondal, Debajyoti
last_name: Mondal
- first_name: Anurag Murty
full_name: Naredla, Anurag Murty
last_name: Naredla
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Alexi
full_name: Turcotte, Alexi
last_name: Turcotte
citation:
ama: Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. Discrete Mathematics
and Theoretical Computer Science. 2023;24(2). doi:10.46298/DMTCS.8383
apa: Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte,
A. (2023). Token swapping on trees. Discrete Mathematics and Theoretical Computer
Science. EPI Sciences. https://doi.org/10.46298/DMTCS.8383
chicago: Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow,
Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token
Swapping on Trees.” Discrete Mathematics and Theoretical Computer Science.
EPI Sciences, 2023. https://doi.org/10.46298/DMTCS.8383.
ieee: A. Biniaz et al., “Token swapping on trees,” Discrete Mathematics
and Theoretical Computer Science, vol. 24, no. 2. EPI Sciences, 2023.
ista: Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec
J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical
Computer Science. 24(2), 9.
mla: Biniaz, Ahmad, et al. “Token Swapping on Trees.” Discrete Mathematics and
Theoretical Computer Science, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:10.46298/DMTCS.8383.
short: A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla,
J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science
24 (2023).
date_created: 2023-04-16T22:01:08Z
date_published: 2023-01-18T00:00:00Z
date_updated: 2024-01-04T12:42:09Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
- _id: HeEd
- _id: UlWa
doi: 10.46298/DMTCS.8383
external_id:
arxiv:
- '1903.06981'
file:
- access_level: open_access
checksum: 439102ea4f6e2aeefd7107dfb9ccf532
content_type: application/pdf
creator: dernst
date_created: 2023-04-17T08:10:28Z
date_updated: 2023-04-17T08:10:28Z
file_id: '12844'
file_name: 2022_DMTCS_Biniaz.pdf
file_size: 2072197
relation: main_file
success: 1
file_date_updated: 2023-04-17T08:10:28Z
has_accepted_license: '1'
intvolume: ' 24'
issue: '2'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
publication: Discrete Mathematics and Theoretical Computer Science
publication_identifier:
eissn:
- 1365-8050
issn:
- 1462-7264
publication_status: published
publisher: EPI Sciences
quality_controlled: '1'
related_material:
record:
- id: '7950'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Token swapping on trees
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2023'
...
---
_id: '11938'
abstract:
- lang: eng
text: A matching is compatible to two or more labeled point sets of size n with
labels {1, . . . , n} if its straight-line drawing on each of these point sets
is crossing-free. We study the maximum number of edges in a matching compatible
to two or more labeled point sets in general position in the plane. We show that
for any two labeled sets of n points in convex position there exists a compatible
matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets
we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound,
we use probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1))
edges. Finally, we show that Θ(log n) copies of any set of n points are necessary
and sufficient for the existence of labelings of these point sets such that any
compatible matching consists only of a single edge.
acknowledgement: 'A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
Journal of Graph Algorithms and Applications. 2022;26(2):225-240. doi:10.7155/jgaa.00591
apa: Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. Journal of Graph
Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00591
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” Journal of Graph Algorithms and Applications. Brown University,
2022. https://doi.org/10.7155/jgaa.00591.
ieee: O. Aichholzer et al., “On compatible matchings,” Journal of Graph
Algorithms and Applications, vol. 26, no. 2. Brown University, pp. 225–240,
2022.
ista: Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and
Applications. 26(2), 225–240.
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” Journal of Graph Algorithms
and Applications, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:10.7155/jgaa.00591.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022)
225–240.
date_created: 2022-08-21T22:01:56Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-02-23T13:54:21Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.7155/jgaa.00591
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
file:
- access_level: open_access
checksum: dc6e255e3558faff924fd9e370886c11
content_type: application/pdf
creator: dernst
date_created: 2022-08-22T06:42:42Z
date_updated: 2022-08-22T06:42:42Z
file_id: '11940'
file_name: 2022_JourGraphAlgorithmsApplic_Aichholzer.pdf
file_size: 694538
relation: main_file
success: 1
file_date_updated: 2022-08-22T06:42:42Z
has_accepted_license: '1'
intvolume: ' 26'
issue: '2'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 225-240
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Journal of Graph Algorithms and Applications
publication_identifier:
issn:
- 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
related_material:
record:
- id: '9296'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 26
year: '2022'
...
---
_id: '8317'
abstract:
- lang: eng
text: When can a polyomino piece of paper be folded into a unit cube? Prior work
studied tree-like polyominoes, but polyominoes with holes remain an intriguing
open problem. We present sufficient conditions for a polyomino with one or several
holes to fold into a cube, and conditions under which cube folding is impossible.
In particular, we show that all but five special “basic” holes guarantee foldability.
acknowledgement: This research was performed in part at the 33rd Bellairs Winter Workshop
on Computational Geometry. We thank all other participants for a fruitful atmosphere.
H. Akitaya was supported by NSF CCF-1422311 & 1423615. Z. Masárová was partially
funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.
article_number: '101700'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Hugo A.
full_name: Akitaya, Hugo A.
last_name: Akitaya
- first_name: Kenneth C.
full_name: Cheung, Kenneth C.
last_name: Cheung
- first_name: Erik D.
full_name: Demaine, Erik D.
last_name: Demaine
- first_name: Martin L.
full_name: Demaine, Martin L.
last_name: Demaine
- first_name: Sándor P.
full_name: Fekete, Sándor P.
last_name: Fekete
- first_name: Linda
full_name: Kleist, Linda
last_name: Kleist
- first_name: Irina
full_name: Kostitsyna, Irina
last_name: Kostitsyna
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- 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: Klara
full_name: Mundilova, Klara
last_name: Mundilova
- first_name: Christiane
full_name: Schmidt, Christiane
last_name: Schmidt
citation:
ama: 'Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes
into a cube. Computational Geometry: Theory and Applications. 2021;93.
doi:10.1016/j.comgeo.2020.101700'
apa: 'Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M.
L., Fekete, S. P., … Schmidt, C. (2021). Folding polyominoes with holes into a
cube. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2020.101700'
chicago: 'Aichholzer, Oswin, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine,
Martin L. Demaine, Sándor P. Fekete, Linda Kleist, et al. “Folding Polyominoes
with Holes into a Cube.” Computational Geometry: Theory and Applications.
Elsevier, 2021. https://doi.org/10.1016/j.comgeo.2020.101700.'
ieee: 'O. Aichholzer et al., “Folding polyominoes with holes into a cube,”
Computational Geometry: Theory and Applications, vol. 93. Elsevier, 2021.'
ista: 'Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist
L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. 2021. Folding
polyominoes with holes into a cube. Computational Geometry: Theory and Applications.
93, 101700.'
mla: 'Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Computational
Geometry: Theory and Applications, vol. 93, 101700, Elsevier, 2021, doi:10.1016/j.comgeo.2020.101700.'
short: 'O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P.
Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt,
Computational Geometry: Theory and Applications 93 (2021).'
date_created: 2020-08-30T22:01:09Z
date_published: 2021-02-01T00:00:00Z
date_updated: 2023-08-04T10:57:42Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2020.101700
external_id:
arxiv:
- '1910.09917'
isi:
- '000579185100004'
intvolume: ' 93'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1910.09917v3
month: '02'
oa: 1
oa_version: Preprint
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- '09257721'
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '6989'
relation: shorter_version
status: public
scopus_import: '1'
status: public
title: Folding polyominoes with holes into a cube
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 93
year: '2021'
...
---
_id: '9296'
abstract:
- lang: eng
text: ' matching is compatible to two or more labeled point sets of size n with
labels {1,…,n} if its straight-line drawing on each of these point sets is
crossing-free. We study the maximum number of edges in a matching compatible to
two or more labeled point sets in general position in the plane. We show that
for any two labeled convex sets of n points there exists a compatible matching
with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct
compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use
probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges.
Finally, we show that Θ(logn) copies of any set of n points are necessary and
sufficient for the existence of a labeling such that any compatible matching consists
only of a single edge.'
acknowledgement: 'A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
In: 15th International Conference on Algorithms and Computation. Vol 12635.
Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18'
apa: 'Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International
Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon,
Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18'
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” In 15th International Conference on Algorithms and Computation,
12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.
ieee: O. Aichholzer et al., “On compatible matchings,” in 15th International
Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635,
pp. 221–233.
ista: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference
on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol.
12635, 221–233.'
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International
Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021,
pp. 221–33, doi:10.1007/978-3-030-68211-8_18.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and
Computation, Springer Nature, 2021, pp. 221–233.
conference:
end_date: 2021-03-02
location: Yangon, Myanmar
name: 'WALCOM: Algorithms and Computation'
start_date: 2021-02-28
date_created: 2021-03-28T22:01:41Z
date_published: 2021-02-16T00:00:00Z
date_updated: 2023-02-21T16:33:44Z
day: '16'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.1007/978-3-030-68211-8_18
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
intvolume: ' 12635'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2101.03928
month: '02'
oa: 1
oa_version: Preprint
page: 221-233
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: 15th International Conference on Algorithms and Computation
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030682101'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11938'
relation: later_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 12635
year: '2021'
...
---
_id: '7944'
abstract:
- lang: eng
text: "This thesis considers two examples of reconfiguration problems: flipping
edges in edge-labelled triangulations of planar point sets and swapping labelled
tokens placed on vertices of a graph. In both cases the studied structures – all
the triangulations of a given point set or all token placements on a given graph
– can be thought of as vertices of the so-called reconfiguration graph, in which
two vertices are adjacent if the corresponding structures differ by a single elementary
operation – by a flip of a diagonal in a triangulation or by a swap of tokens
on adjacent vertices, respectively. We study the reconfiguration of one instance
of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor
triangulations of point sets in which each edge has a unique label and a flip
transfers the label from the removed edge to the new edge, we prove a polynomial-time
testable condition, called the Orbit Theorem, that characterizes when two triangulations
of the same point set lie in the same connected component of the reconfiguration
graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot.
We additionally provide a polynomial time algorithm that computes a reconfiguring
flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties
of a certain high-dimensional cell complex that has the usual reconfiguration
graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph,
we make partial progress on the problem of finding shortest reconfiguration sequences.
We disprove the so-called Happy Leaf Conjecture and demonstrate the importance
of swapping tokens that are already placed at the correct vertices. We also prove
that a generalization of the problem to weighted coloured token swapping is NP-hard
on trees but solvable in polynomial time on paths and stars."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
citation:
ama: Masárová Z. Reconfiguration problems. 2020. doi:10.15479/AT:ISTA:7944
apa: Masárová, Z. (2020). Reconfiguration problems. Institute of Science
and Technology Austria. https://doi.org/10.15479/AT:ISTA:7944
chicago: Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and
Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944.
ieee: Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology
Austria, 2020.
ista: Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology
Austria.
mla: Masárová, Zuzana. Reconfiguration Problems. Institute of Science and
Technology Austria, 2020, doi:10.15479/AT:ISTA:7944.
short: Z. Masárová, Reconfiguration Problems, Institute of Science and Technology
Austria, 2020.
date_created: 2020-06-08T00:49:46Z
date_published: 2020-06-09T00:00:00Z
date_updated: 2023-09-07T13:17:37Z
day: '09'
ddc:
- '516'
- '514'
degree_awarded: PhD
department:
- _id: HeEd
- _id: UlWa
doi: 10.15479/AT:ISTA:7944
file:
- access_level: open_access
checksum: df688bc5a82b50baee0b99d25fc7b7f0
content_type: application/pdf
creator: zmasarov
date_created: 2020-06-08T00:34:00Z
date_updated: 2020-07-14T12:48:05Z
file_id: '7945'
file_name: THESIS_Zuzka_Masarova.pdf
file_size: 13661779
relation: main_file
- access_level: closed
checksum: 45341a35b8f5529c74010b7af43ac188
content_type: application/zip
creator: zmasarov
date_created: 2020-06-08T00:35:30Z
date_updated: 2020-07-14T12:48:05Z
file_id: '7946'
file_name: THESIS_Zuzka_Masarova_SOURCE_FILES.zip
file_size: 32184006
relation: source_file
file_date_updated: 2020-07-14T12:48:05Z
has_accepted_license: '1'
keyword:
- reconfiguration
- reconfiguration graph
- triangulations
- flip
- constrained triangulations
- shellability
- piecewise-linear balls
- token swapping
- trees
- coloured weighted token swapping
language:
- iso: eng
license: https://creativecommons.org/licenses/by-sa/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: '160'
publication_identifier:
isbn:
- 978-3-99078-005-3
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '7950'
relation: part_of_dissertation
status: public
- id: '5986'
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
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
title: Reconfiguration problems
tmp:
image: /images/cc_by_sa.png
legal_code_url: https://creativecommons.org/licenses/by-sa/4.0/legalcode
name: Creative Commons Attribution-ShareAlike 4.0 International Public License (CC
BY-SA 4.0)
short: CC BY-SA (4.0)
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_id: '7950'
abstract:
- lang: eng
text: "The input to the token swapping problem is a graph with vertices v1, v2,
. . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The
goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number
of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token
swapping on a tree, also known as “sorting with a transposition tree,” is not
known to be in P nor NP-complete. We present some partial results:\r\n1. An
optimum swap sequence may need to perform a swap on a leaf vertex that has the
correct token (a “happy leaf”), disproving a conjecture of Vaughan.\r\n2. Any
algorithm that fixes happy leaves—as all known approximation algorithms for the
problem do—has approximation factor at least 4/3. Furthermore, the two best-known
2-approximation algorithms have approximation factor exactly 2.\r\n3. A generalized
problem—weighted coloured token swapping—is NP-complete on trees, but solvable
in polynomial time on paths and stars. In this version, tokens and vertices
\ have colours, and colours have weights. The goal is to get every
token to a vertex of the same colour, and the cost of a swap is the sum of the
weights of the two tokens involved."
article_number: '1903.06981'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ahmad
full_name: Biniaz, Ahmad
last_name: Biniaz
- first_name: Kshitij
full_name: Jain, Kshitij
last_name: Jain
- 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: Tillmann
full_name: Miltzow, Tillmann
last_name: Miltzow
- first_name: Debajyoti
full_name: Mondal, Debajyoti
last_name: Mondal
- first_name: Anurag Murty
full_name: Naredla, Anurag Murty
last_name: Naredla
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Alexi
full_name: Turcotte, Alexi
last_name: Turcotte
citation:
ama: Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. arXiv.
apa: Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte,
A. (n.d.). Token swapping on trees. arXiv.
chicago: Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow,
Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token
Swapping on Trees.” ArXiv, n.d.
ieee: A. Biniaz et al., “Token swapping on trees,” arXiv. .
ista: Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec
J, Turcotte A. Token swapping on trees. arXiv, 1903.06981.
mla: Biniaz, Ahmad, et al. “Token Swapping on Trees.” ArXiv, 1903.06981.
short: A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla,
J. Tkadlec, A. Turcotte, ArXiv (n.d.).
date_created: 2020-06-08T12:25:25Z
date_published: 2019-03-16T00:00:00Z
date_updated: 2024-01-04T12:42:08Z
day: '16'
department:
- _id: HeEd
- _id: UlWa
- _id: KrCh
external_id:
arxiv:
- '1903.06981'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1903.06981
month: '03'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
related_material:
record:
- id: '7944'
relation: dissertation_contains
status: public
- id: '12833'
relation: later_version
status: public
status: public
title: Token swapping on trees
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...
---
_id: '6989'
abstract:
- lang: eng
text: 'When can a polyomino piece of paper be folded into a unit cube? Prior work
studied tree-like polyominoes, but polyominoes with holes remain an intriguing
open problem. We present sufficient conditions for a polyomino with hole(s) to
fold into a cube, and conditions under which cube folding is impossible. In particular,
we show that all but five special simple holes guarantee foldability. '
acknowledgement: This research was performed in part at the 33rd BellairsWinter Workshop on Computational Geometry. Wethank
all other participants for a fruitful atmosphere.
article_processing_charge: No
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Hugo A
full_name: Akitaya, Hugo A
last_name: Akitaya
- first_name: Kenneth C
full_name: Cheung, Kenneth C
last_name: Cheung
- first_name: Erik D
full_name: Demaine, Erik D
last_name: Demaine
- first_name: Martin L
full_name: Demaine, Martin L
last_name: Demaine
- first_name: Sandor P
full_name: Fekete, Sandor P
last_name: Fekete
- first_name: Linda
full_name: Kleist, Linda
last_name: Kleist
- first_name: Irina
full_name: Kostitsyna, Irina
last_name: Kostitsyna
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- 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: Klara
full_name: Mundilova, Klara
last_name: Mundilova
- first_name: Christiane
full_name: Schmidt, Christiane
last_name: Schmidt
citation:
ama: 'Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes
into a cube. In: Proceedings of the 31st Canadian Conference on Computational
Geometry. Canadian Conference on Computational Geometry; 2019:164-170.'
apa: 'Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M.
L., Fekete, S. P., … Schmidt, C. (2019). Folding polyominoes with holes into a
cube. In Proceedings of the 31st Canadian Conference on Computational Geometry
(pp. 164–170). Edmonton, Canada: Canadian Conference on Computational Geometry.'
chicago: Aichholzer, Oswin, Hugo A Akitaya, Kenneth C Cheung, Erik D Demaine, Martin
L Demaine, Sandor P Fekete, Linda Kleist, et al. “Folding Polyominoes with Holes
into a Cube.” In Proceedings of the 31st Canadian Conference on Computational
Geometry, 164–70. Canadian Conference on Computational Geometry, 2019.
ieee: O. Aichholzer et al., “Folding polyominoes with holes into a cube,”
in Proceedings of the 31st Canadian Conference on Computational Geometry,
Edmonton, Canada, 2019, pp. 164–170.
ista: 'Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist
L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. 2019. Folding
polyominoes with holes into a cube. Proceedings of the 31st Canadian Conference
on Computational Geometry. CCCG: Canadian Conference in Computational Geometry,
164–170.'
mla: Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Proceedings
of the 31st Canadian Conference on Computational Geometry, Canadian Conference
on Computational Geometry, 2019, pp. 164–70.
short: O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P.
Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt,
in:, Proceedings of the 31st Canadian Conference on Computational Geometry, Canadian
Conference on Computational Geometry, 2019, pp. 164–170.
conference:
end_date: 2019-08-10
location: Edmonton, Canada
name: 'CCCG: Canadian Conference in Computational Geometry'
start_date: 2019-08-08
date_created: 2019-11-04T16:46:11Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-08-04T10:57:42Z
day: '01'
department:
- _id: HeEd
external_id:
arxiv:
- '1910.09917'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://cccg.ca/proceedings/2019/proceedings.pdf
month: '08'
oa: 1
oa_version: Published Version
page: 164-170
publication: Proceedings of the 31st Canadian Conference on Computational Geometry
publication_status: published
publisher: Canadian Conference on Computational Geometry
quality_controlled: '1'
related_material:
record:
- id: '8317'
relation: extended_version
status: public
scopus_import: '1'
status: public
title: Folding polyominoes with holes into a cube
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
year: '2019'
...
---
_id: '5986'
abstract:
- lang: eng
text: "Given a triangulation of a point set in the plane, a flip deletes an edge
e whose removal leaves a convex quadrilateral, and replaces e by the opposite
diagonal of the quadrilateral. It is well known that any triangulation of a point
set can be reconfigured to any other triangulation by some sequence of flips.
We explore this question in the setting where each edge of a triangulation has
a label, and a flip transfers the label of the removed edge to the new edge. It
is not true that every labelled triangulation of a point set can be reconfigured
to every other labelled triangulation via a sequence of flips, but we characterize
when this is possible. There is an obvious necessary condition: for each label
l, if edge e has label l in the first triangulation and edge f has label l in
the second triangulation, then there must be some sequence of flips that moves
label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot
formulated the Orbit Conjecture, which states that this necessary condition is
also sufficient, i.e. that all labels can be simultaneously mapped to their destination
if and only if each label individually can be mapped to its destination. We prove
this conjecture. Furthermore, we give a polynomial-time algorithm (with \U0001D442(\U0001D45B8)
being a crude bound on the run-time) to find a sequence of flips to reconfigure
one labelled triangulation to another, if such a sequence exists, and we prove
an upper bound of \U0001D442(\U0001D45B7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges
on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional
ball (this follows from a result of Orden and Santos; we give a different proof
based on a shelling argument). The dual cell complex of this simplicial ball,
called the flip complex, has the usual flip graph as its 1-skeleton. We use properties
of the 2-skeleton of the flip complex to prove the Orbit Conjecture."
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 2019;61(4):880-898.
doi:10.1007/s00454-018-0035-8
apa: Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture
for flipping edge-labelled triangulations. Discrete & Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-018-0035-8
chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry.
Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.
ieee: A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for
flipping edge-labelled triangulations,” Discrete & Computational Geometry,
vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.
ista: Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.
mla: Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled
Triangulations.” Discrete & Computational Geometry, vol. 61, no. 4,
Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.
short: A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61
(2019) 880–898.
date_created: 2019-02-14T11:54:08Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:17:36Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
external_id:
arxiv:
- '1710.02741'
isi:
- '000466130000009'
file:
- access_level: open_access
checksum: e1bff88f1d77001b53b78c485ce048d7
content_type: application/pdf
creator: dernst
date_created: 2019-02-14T11:57:22Z
date_updated: 2020-07-14T12:47:14Z
file_id: '5988'
file_name: 2018_DiscreteGeometry_Lubiw.pdf
file_size: 556276
relation: main_file
file_date_updated: 2020-07-14T12:47:14Z
has_accepted_license: '1'
intvolume: ' 61'
isi: 1
issue: '4'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 880-898
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '683'
relation: earlier_version
status: public
- id: '7944'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: A proof of the orbit conjecture for flipping edge-labelled triangulations
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 61
year: '2019'
...
---
_id: '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'
...