We explore the application of graph database technology to spatio-temporal model checking of cooperating cyber-physical systems-of-systems such as vehicle platoons. We present a translation of spatio-temporal automata(STA) and the spatio-temporal logic STAL to se-mantically equivalent property graphs and graph queries respectively. We prove a sound reduction of the spatio-temporal verification problem tograph database query solving. The practicability and efficiency of thisapproach is evaluated by introducing NeoMC, a prototype implementation of our explicit model checking approach based on Neo4j. To evaluate NeoMC we consider case studies of verifying vehicle platooning models. Our evaluation demonstrates the effectiveness of our approach in terms of execution time and counterexample detection.