I’ll go on record saying +1 for including NetworkX as a required dependency. It’s a big decision, but here’s why:

The third point is the reason I favor a required dependency rather than an optional one. At present making it an optional dependency would not be that difficult, but if we make it required we can build on it without constant concern of fallback code paths or functions which just won’t exist if NetworkX is missing. Also, this would ensure our full package is exposed to the most users; e.g., Anaconda/Canopy/pip fetch and build required dependencies but not all have elegant provisions for optional ones.

If NetworkX weren’t mature and/or if NetworkX didn’t share dependencies with scikit-image, my answer would be different.