Flexible placements of graphs with rotational symmetry

Sean Dewar; Georg Grasegger; Jan Legerský

doi:10.1007/978-3-030-91352-6_9

Flexible placements of graphs with rotational symmetry

Sean Dewar, Georg Grasegger, Jan Legerský

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

2 Citations (Scopus)

3 Downloads (Pure)

Abstract

We study the existence of an $n$-fold rotationally symmetric placement of a symmetric graph in the plane allowing a continuous deformation that preserves the symmetry and the distances between adjacent vertices. We show that such a flexible placement exists if and only if the graph has a NAC-colouring satisfying an additional property on the symmetry; a NAC-colouring is a surjective edge colouring by two colours such that every cycle is either monochromatic, or there are at least two edges of each colour.

Original language	English
Title of host publication	2nd IMA Conference on Mathematics of Robotics, IMA 2020
Editors	William Holderbaum, J. M Selig
Publisher	Springer
Chapter	9
Pages	89–97
Number of pages	9
Volume	21
ISBN (Electronic)	9783030913526
ISBN (Print)	9783030913519
DOIs	https://doi.org/10.1007/978-3-030-91352-6_9
Publication status	Published - 21 Nov 2023

Publication series

Name	Springer Proceedings in Advanced Robotics
Volume	21 SPAR
ISSN (Print)	2511-1256
ISSN (Electronic)	2511-1264

Bibliographical note

Funding Information:
Acknowledgments. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 675789. The project was supported by the Austrian Science Fund (FWF): P31061, P31888 and W1214-N15, and by the Ministry of Education, Youth and Sports of the Czech Republic, project no. CZ.02.1.01/0.0/ 0.0/16 019/0000778.

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

math.CO
cs.RO
math.MG
52C25, 51K99, 70B99, 05C78

Access to Document

10.1007/978-3-030-91352-6_9Licence: Unspecified

Handle.net

Persistent link

Embargoed Document

Full-text PDF (accepted manuscript)
Accepted author manuscript, 164 KB
Licence: Unspecified
Embargo ends: 21/11/25
Request copy

Cite this

@inproceedings{50df90b614c748b785a5f9ab63db6334,

title = "Flexible placements of graphs with rotational symmetry",

abstract = "We study the existence of an $n$-fold rotationally symmetric placement of a symmetric graph in the plane allowing a continuous deformation that preserves the symmetry and the distances between adjacent vertices. We show that such a flexible placement exists if and only if the graph has a NAC-colouring satisfying an additional property on the symmetry; a NAC-colouring is a surjective edge colouring by two colours such that every cycle is either monochromatic, or there are at least two edges of each colour.",

keywords = "math.CO, cs.RO, math.MG, 52C25, 51K99, 70B99, 05C78",

author = "Sean Dewar and Georg Grasegger and Jan Legersk{\'y}",

note = "Funding Information: Acknowledgments. This project has received funding from the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 675789. The project was supported by the Austrian Science Fund (FWF): P31061, P31888 and W1214-N15, and by the Ministry of Education, Youth and Sports of the Czech Republic, project no. CZ.02.1.01/0.0/ 0.0/16 019/0000778. Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2023",

month = nov,

day = "21",

doi = "10.1007/978-3-030-91352-6_9",

language = "English",

isbn = "9783030913519",

volume = "21",

series = "Springer Proceedings in Advanced Robotics",

publisher = "Springer",

pages = "89–97",

editor = "William Holderbaum and Selig, {J. M}",

booktitle = "2nd IMA Conference on Mathematics of Robotics, IMA 2020",

}

Flexible placements of graphs with rotational symmetry. / Dewar, Sean; Grasegger, Georg; Legerský, Jan.
2nd IMA Conference on Mathematics of Robotics, IMA 2020. ed. / William Holderbaum; J. M Selig. Vol. 21 Springer, 2023. p. 89–97 (Springer Proceedings in Advanced Robotics; Vol. 21 SPAR).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Flexible placements of graphs with rotational symmetry

AU - Dewar, Sean

AU - Grasegger, Georg

AU - Legerský, Jan

N1 - Funding Information: Acknowledgments. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 675789. The project was supported by the Austrian Science Fund (FWF): P31061, P31888 and W1214-N15, and by the Ministry of Education, Youth and Sports of the Czech Republic, project no. CZ.02.1.01/0.0/ 0.0/16 019/0000778. Publisher Copyright: © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2023/11/21

Y1 - 2023/11/21

N2 - We study the existence of an $n$-fold rotationally symmetric placement of a symmetric graph in the plane allowing a continuous deformation that preserves the symmetry and the distances between adjacent vertices. We show that such a flexible placement exists if and only if the graph has a NAC-colouring satisfying an additional property on the symmetry; a NAC-colouring is a surjective edge colouring by two colours such that every cycle is either monochromatic, or there are at least two edges of each colour.

AB - We study the existence of an $n$-fold rotationally symmetric placement of a symmetric graph in the plane allowing a continuous deformation that preserves the symmetry and the distances between adjacent vertices. We show that such a flexible placement exists if and only if the graph has a NAC-colouring satisfying an additional property on the symmetry; a NAC-colouring is a surjective edge colouring by two colours such that every cycle is either monochromatic, or there are at least two edges of each colour.

KW - math.CO

KW - cs.RO

KW - math.MG

KW - 52C25, 51K99, 70B99, 05C78

U2 - 10.1007/978-3-030-91352-6_9

DO - 10.1007/978-3-030-91352-6_9

M3 - Conference Contribution (Conference Proceeding)

SN - 9783030913519

VL - 21

T3 - Springer Proceedings in Advanced Robotics

SP - 89

EP - 97

BT - 2nd IMA Conference on Mathematics of Robotics, IMA 2020

A2 - Holderbaum, William

A2 - Selig, J. M

PB - Springer

ER -

Flexible placements of graphs with rotational symmetry

Abstract

Publication series

Bibliographical note

Keywords

Access to Document

Handle.net

Embargoed Document

Fingerprint

Cite this