spatial_graph uses witty to compile the C/C++ parts during runtime and load them as a module. witty, in turn, uses cython.
My take is that in environments that can successfully install cython packages that are build at install time, spatial_graph should also compile without issues. The underlying mechanism is the same. It's possible that if someone runs spatial_graph from within an IDE there could be interference with their PATH or other environment variables, which could affect compilation (hi @tlambert03!).
For windows users, that seems to mean that they have to install a compiler (MSVC or MinGW). I'm not familiar with those. Would it be enough to include msvc-runtime in the dependencies?