[1] https://news.ycombinator.com/item?id=27294401
For example, node-based editors in game engines and other media software need a few key algorithms, but the ordering of incoming/outgoing edges have meaningful semantics that might need to be considered.
You may need to use a custom algorithm to write a solver for a particular problem, for example latency/delay compensation in various networks (audio, distributed sensors, etc).
Other times you may want to combine multiple algorithms into single traversals, which is often used in single-pass compilers or parsers. These can be tricky if the traversal modifies the graph.
Then there are hypergraphs, which are so generic you probably need to treat your application as a special case.
For applications, compilers need graph coloring. Task schedulers need graph cuts. Since these are NP complete there is plenty of room for research on specific implementations with various heuristics.