The most difficult part I think would be to make entering graph nodes ergonomic. In my experience, these kinds of tools live and die by the speed at which you can enter, modify and move things around in them. If you have to click a lot and type data in a bunch of forms, developer won't be using it.
Example: that time when I first compiled the list of desired features, we were trying out YouTrack from JetBrains. My co-worker liked it, but found entering subtasks annoying. I wrote a little script inside YouTrack that turned every Markdown checklist into new tickets, backlinked to the parent one. A total hack, but made a big qualitative difference in terms of working with the tool.
The key two principles for me therefore are:
- Fast to enter and manipulate data in it. Everything doable from keyboard, and little waiting for things to process (hello, Jira).
- Embrace the fact that plans and work subdivisions keep changing all the time. Allow users to restructure their tasks, warn them when they affect other parts of the graph, and just persist the changelog so that a broken graph can be easily fixed.
I have some more ideas in this space, but little time to deal with the surrounding work that's required to turn it into an application prototype.