We have carried out optical spectroscopy with the Anglo-Australian Telescope for 24 726 objects surrounding a sample of 19 giant radio galaxies (GRGs) selected to have redshifts in the range 0.05-0.15 and projected linear sizes from 0.8 to 3.2 Mpc. Such radio galaxies are ideal candidates to study the warm-hot intergalactic medium because their radio lobes extend beyond the interstellar medium and haloes of their host galaxies, and into the tenuous intergalactic medium. We were able to measure redshifts for 9076 galaxies. Radio imaging of each GRG, including high-sensitivity, wide-band radio observations from the Australia Telescope Compact Array for 12 GRGs and host optical spectra (presented in a previous paper), is used in conjunction with the surrounding galaxy redshifts to trace large-scale structure. We find that the mean galaxy number overdensity in volumes of ~700 Mpc3 near the GRG host galaxies is ~70 indicating an overdense but non-virialized environment. A Fourier component analysis is used to quantify the anisotropy in the surrounding galaxy distribution. For GRGs with radio components offset from the radio axis, there is a clear influence of the environment with lobes appearing to be deflected away from overdensities in the surrounding medium. Furthermore, the GRG lobes tend to be normal to the plane defined by the galaxy neighbourhood close to the host. This indicates the tendency for lobes to grow to giant sizes in directions that avoid dense regions on both small and large scales.