Existing kinetic Monte Carlo (KMC) frameworks for the simulation of adsorption, desorption, diffusion, and reaction on a lattice often assume that each participating species occupies a single site and represent elementary events involving a maximum of two sites. However, these assumptions may be inadequate, especially in the case of complex chemistries, involving multidentate species or complex coverage and neighboring patterns between several lattice sites. We have developed a novel approach that employs graph-theoretical ideas to overcome these challenges and treat easily complex chemistries. As a benchmark, the Ziff-Gulari-Barshad system is simulated and comparisons of the computational times of the graph-theoretical KMC and a simpler KMC approach are made. Further, to demonstrate the capabilities of our framework, the water-gas shift chemistry on Pt(111) is simulated.