The main objective of this contribution is to define and characterize a large class of crossover operators for graphs. The key idea is to use cuts in graphs as means of (bi-)partitioning the parents and to recombine the resulting parts by means of a join operation. This very general scheme of cut-and-join crossover subsumes most of the procedures in graph-based GAs applied to chemical space exploration. Instead of implementing specific restrictions motivated by chemical intuition, we start from a very general construction that is not related to chemistry. We proceed to demonstrate that this leads to a class of operators that can be tuned in a very natural fashion to preserve both local properties, such as vertex degrees, as well as certain global properties, such as graph-theoretic planarity, that are of direct relevance for applications in chemistry.