Playing Snake on a Graph

Denise Graafsma; Bodo Manthey; Alexander Skopalik

doi:10.1007/978-3-032-11835-6_17

Playing Snake on a Graph

Denise Graafsma^*
, Bodo Manthey
, Alexander Skopalik

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable.

We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers
Editors	Henning Fernau, Philipp Kindermann
Place of Publication	Cham
Publisher	Springer
Pages	230-243
Number of pages	14
Edition	1
ISBN (Electronic)	978-3-032-11835-6
ISBN (Print)	978-3-032-11834-9
DOIs	https://doi.org/10.1007/978-3-032-11835-6_17
Publication status	Published - 2026
Event	51st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2025 - Europäische Akademie Otzenhausen, Otzenhausen, Germany Duration: 11 Jun 2025 → 13 Jun 2025 Conference number: 51 https://algo.uni-trier.de/wg2025/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	16124 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	51st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2025
Abbreviated title	WG 2025
Country/Territory	Germany
City	Otzenhausen
Period	11/06/25 → 13/06/25
Internet address	https://algo.uni-trier.de/wg2025/

Keywords

2026 OA procedure

Access to Document

10.1007/978-3-032-11835-6_17

Cite this

Graafsma, D., Manthey, B., & Skopalik, A. (2026). Playing Snake on a Graph. In H. Fernau, & P. Kindermann (Eds.), Graph-Theoretic Concepts in Computer Science: 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers (1 ed., pp. 230-243). (Lecture Notes in Computer Science; Vol. 16124 LNCS). Springer. https://doi.org/10.1007/978-3-032-11835-6_17

@inproceedings{4d531e7ad938429a82f9f0bc4b408d02,

title = "Playing Snake on a Graph",

abstract = "Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight.",

keywords = "2026 OA procedure",

author = "Denise Graafsma and Bodo Manthey and Alexander Skopalik",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.; 51st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2025, WG 2025 ; Conference date: 11-06-2025 Through 13-06-2025",

year = "2026",

doi = "10.1007/978-3-032-11835-6\_17",

language = "English",

isbn = "978-3-032-11834-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "230--243",

editor = "Henning Fernau and Philipp Kindermann",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

edition = "1",

url = "https://algo.uni-trier.de/wg2025/",

}

Graafsma, D, Manthey, B & Skopalik, A 2026, Playing Snake on a Graph. in H Fernau & P Kindermann (eds), Graph-Theoretic Concepts in Computer Science: 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers. 1 edn, Lecture Notes in Computer Science, vol. 16124 LNCS, Springer, Cham, pp. 230-243, 51st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2025, Otzenhausen, Saarland, Germany, 11/06/25. https://doi.org/10.1007/978-3-032-11835-6_17

Playing Snake on a Graph. / Graafsma, Denise; Manthey, Bodo ; Skopalik, Alexander.
Graph-Theoretic Concepts in Computer Science: 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers. ed. / Henning Fernau; Philipp Kindermann. 1. ed. Cham: Springer, 2026. p. 230-243 (Lecture Notes in Computer Science; Vol. 16124 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Playing Snake on a Graph

AU - Graafsma, Denise

AU - Manthey, Bodo

AU - Skopalik, Alexander

N1 - Conference code: 51

PY - 2026

Y1 - 2026

N2 - Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight.

AB - Snake is a classic computer game, which has been around for decades. Based on this game, we study the game of Snake on arbitrary undirected graphs. A snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We prove that determining whether a graph is snake-winnable is NP-hard, even when restricted to grid graphs. We fully characterize snake-winnable graphs for odd-sized bipartite graphs and graphs with vertex-connectivity 1. While Hamiltonian graphs are always snake-winnable, we show that non-Hamiltonian snake-winnable graphs have a girth of at most 6 and that this bound is tight.

KW - 2026 OA procedure

UR - https://www.scopus.com/pages/publications/105027566774

U2 - 10.1007/978-3-032-11835-6_17

DO - 10.1007/978-3-032-11835-6_17

M3 - Conference contribution

AN - SCOPUS:105027566774

SN - 978-3-032-11834-9

T3 - Lecture Notes in Computer Science

SP - 230

EP - 243

BT - Graph-Theoretic Concepts in Computer Science

A2 - Fernau, Henning

A2 - Kindermann, Philipp

PB - Springer

CY - Cham

T2 - 51st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2025

Y2 - 11 June 2025 through 13 June 2025

ER -

Graafsma D, Manthey B , Skopalik A. Playing Snake on a Graph. In Fernau H, Kindermann P, editors, Graph-Theoretic Concepts in Computer Science: 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers. 1 ed. Cham: Springer. 2026. p. 230-243. (Lecture Notes in Computer Science). Epub 2026 Jan 2. doi: 10.1007/978-3-032-11835-6_17

Playing Snake on a Graph

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Embargoed Document

Fingerprint

Playing Snake on a Graph

Cite this