The valence-bond structure of spin-1/2 Heisenberg antiferromagnets is closely related to quantum entanglement. We investigate measures of entanglement entropy based on transition graphs, which characterize state overlaps in the overcomplete valence-bond basis. The transition graphs can be generated using projector Monte Carlo simulations of ground states of specific hamiltonians or using importance-sampling of valence-bond configurations of amplitude-product states. We consider definitions of entanglement entropy based on the bonds or loops shared by two subsystems (bipartite entanglement). Results for the bond-based definition agrees with a previously studied definition using valence-bond wave functions (instead of the transition graphs, which involve two states). For the one dimensional Heisenberg chain, with uniform or random coupling constants, the prefactor of the logarithmic divergence with the size of the smaller subsystem agrees with exact results. For the ground state of the two-dimensional Heisenberg model (and also Neel-ordered amplitude-product states), there is a similar multiplicative violation of the area law. In contrast, the loop-based entropy obeys the area law in two dimensions, while still violating it in one dimension - both behaviors in accord with expectations for proper measures of entanglement entropy.