We study geometric presentations of braid groups for particles that are constrained to move on a graph, i.e. a network consisting of nodes and edges. Our proposed set of generators consists of exchanges of pairs of particles on junctions of the graph and of certain circular moves where one particle travels around a simple cycle of the graph. We point out that so defined generators often do not satisfy the braiding relation known from 2D physics. We accomplish a full description of relations between the generators for star graphs where we derive certain quasi-braiding relations. We also describe how graph braid groups depend on the (graph-theoretic) connectivity of the graph. This is done in terms of quotients of graph braid groups where one-particle moves are put to identity. In particular, we show that for 3-connected planar graphs such a quotient reconstructs the well-known planar braid group. For 2-connected graphs this approach leads to generalisations of the Yang–Baxter equation. Our results are of particular relevance for the study of non-abelian anyons on networks showing new possibilities for non-abelian quantum statistics on graphs.