Flipping Plane Spanning Paths

Oswin Aichholzer; Kristin Knorr; Maarten Löffler; Zuzana Masárová; Wolfgang Mulzer; Johannes Obenaus; Rosna Paul; Birgit Vogtenhuber

Flipping Plane Spanning Paths

Oswin Aichholzer, Kristin Knorr, Maarten Löffler, Zuzana Masárová, Wolfgang Mulzer, Johannes Obenaus, Rosna Paul, Birgit Vogtenhuber

Institut für Softwaretechnologie (7160)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

Abstract

Let S be a planar point set in general position, and let P(S) be the set of all plane (straight-line) spanning paths for S. A flip in a path P ∈ P(S) is the operation of removing an edge e ∈ P and replacing it with a new edge f on S such that the resulting graph is again a path in P(S). Towards the question whether any two plane spanning paths of P(S) can be transformed into each other by a sequence of flips, we give positive answers if S is a wheel set, an ice cream cone, or a double chain.
On the other hand, we show that in the general setting, it is sufficient to prove the statement for plane spanning paths with fixed first edge

Originalsprache	englisch
Titel	Proc. 38th European Workshop on Computational Geometry (EuroCG 2022)
Erscheinungsort	Perugia, Italy
Seiten	66:1-66:7
Publikationsstatus	Veröffentlicht - 2022
Veranstaltung	38th European Workshop on Computational Geometry: EuroCG 2022 - Engineering Department of the University of Perugia, Perugia, Italien Dauer: 14 März 2022 → 16 März 2022 https://eurocg2022.unipg.it/

Konferenz

Konferenz	38th European Workshop on Computational Geometry
Kurztitel	EuroCG 2022
Land/Gebiet	Italien
Ort	Perugia
Zeitraum	14/03/22 → 16/03/22
Internetadresse	https://eurocg2022.unipg.it/

Fields of Expertise

Information, Communication & Computing

38th European Workshop on Computational Geometry
Rosna Paul (Teilnehmer/-in)
14 März 2022 → 16 März 2022
Aktivität: Teilnahme an / Organisation von › Workshop, Seminar oder Kurs (Teilnahme an/Organisation von)

Dieses zitieren

@inproceedings{74ba823d742d4253a57de6dad4262d38,

title = "Flipping Plane Spanning Paths",

abstract = "Let S be a planar point set in general position, and let P(S) be the set of all plane (straight-line) spanning paths for S. A flip in a path P ∈ P(S) is the operation of removing an edge e ∈ P and replacing it with a new edge f on S such that the resulting graph is again a path in P(S). Towards the question whether any two plane spanning paths of P(S) can be transformed into each other by a sequence of flips, we give positive answers if S is a wheel set, an ice cream cone, or a double chain.On the other hand, we show that in the general setting, it is sufficient to prove the statement for plane spanning paths with fixed first edge",

author = "Oswin Aichholzer and Kristin Knorr and Maarten L{\"o}ffler and Zuzana Mas{\'a}rov{\'a} and Wolfgang Mulzer and Johannes Obenaus and Rosna Paul and Birgit Vogtenhuber",

year = "2022",

language = "English",

pages = "66:1--66:7",

booktitle = "Proc. 38th European Workshop on Computational Geometry (EuroCG 2022)",

note = "38th European Workshop on Computational Geometry : EuroCG 2022, EuroCG 2022 ; Conference date: 14-03-2022 Through 16-03-2022",

url = "https://eurocg2022.unipg.it/",

}

TY - GEN

T1 - Flipping Plane Spanning Paths

AU - Aichholzer, Oswin

AU - Knorr, Kristin

AU - Löffler, Maarten

AU - Masárová, Zuzana

AU - Mulzer, Wolfgang

AU - Obenaus, Johannes

AU - Paul, Rosna

AU - Vogtenhuber, Birgit

PY - 2022

Y1 - 2022

N2 - Let S be a planar point set in general position, and let P(S) be the set of all plane (straight-line) spanning paths for S. A flip in a path P ∈ P(S) is the operation of removing an edge e ∈ P and replacing it with a new edge f on S such that the resulting graph is again a path in P(S). Towards the question whether any two plane spanning paths of P(S) can be transformed into each other by a sequence of flips, we give positive answers if S is a wheel set, an ice cream cone, or a double chain.On the other hand, we show that in the general setting, it is sufficient to prove the statement for plane spanning paths with fixed first edge

AB - Let S be a planar point set in general position, and let P(S) be the set of all plane (straight-line) spanning paths for S. A flip in a path P ∈ P(S) is the operation of removing an edge e ∈ P and replacing it with a new edge f on S such that the resulting graph is again a path in P(S). Towards the question whether any two plane spanning paths of P(S) can be transformed into each other by a sequence of flips, we give positive answers if S is a wheel set, an ice cream cone, or a double chain.On the other hand, we show that in the general setting, it is sufficient to prove the statement for plane spanning paths with fixed first edge

M3 - Conference paper

SP - 66:1-66:7

BT - Proc. 38th European Workshop on Computational Geometry (EuroCG 2022)

CY - Perugia, Italy

T2 - 38th European Workshop on Computational Geometry

Y2 - 14 March 2022 through 16 March 2022

ER -

Flipping Plane Spanning Paths

Abstract

Konferenz

Fields of Expertise

Fingerprint

Aktivitäten

38th European Workshop on Computational Geometry

Dieses zitieren