LIPIcs.SoCG.2021.62.pdf
- Filesize: 2.07 MB
- 4 pages
Document
Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition)
Authors
Aaron T. Becker 
,
Sándor P. Fekete ,
Matthias Konitzny ,
Sebastian Morr ,
Arne Schmidt
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
File
Document Identifiers
Author Details
Cite As Get BibTex
Aaron T. Becker, Sándor P. Fekete, Matthias Konitzny, Sebastian Morr, and Arne Schmidt. Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 62:1-62:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.62
Abstract
We illustrate and animate the classic problem of deciding whether a given graph has an Eulerian path. Starting with a collection of instances of increasing difficulty, we present a set of pictorial instructions, and show how they can be used to solve all instances. These IDEA instructions ("A series of nonverbal algorithm assembly instructions") have proven to be both entertaining for experts and enlightening for novices. We (w)rap up with a song and dance to Euler’s original instance.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Discrete mathematics
- Applied computing → Education
Keywords
- Eulerian tours
- algorithms
- education
- IDEA instructions
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Blanche Descartes. The expanding unicurse. In Frank Harari, editor, Proof Techniques in Graph Theory, page 25. Academic Press, 1969.
-
Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, pages 128-140, 1741.
- Sándor P. Fekete and Sebastian Morr. IDEA instructions. https://idea-instructions.com, 2018.
-
M Fleury. Deux problèmes de géometrie de situation. Journal de mathematiques éleméntaires, 2(2):257-261, 1883.
-
Karen A Frenkel. An interview with the 1986 ACM Turing award recipients - John E. Hopcroft and Robert E. Tarjan. Communications of the ACM, 30(3):214-222, 1987.
-
Carl Hierholzer and Chr Wiener. Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6(1):30-32, 1873.