This volume constitutes the thoroughly refereed proceedings of the 51st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2025, which took place in Otzenhausen, Germany, during June 2025.

The 32 full papers included in this book were carefully reviewed and selected from 91 submissions. The deal with applications of graph theory to various areas in computer science focusing on design and analysis of sequential, parallel, randomized, parameterized algorithms; distributed graph and network algorithms; structural graph theory with algorithmic or complexity applications; computational complexity of graph and network problems; graph grammars, graph rewriting systems and graph modeling; etc.