Though its flash, it seems very interesting, and they have at least tree visualization, though you may be able to coax some non-directed graphs out of it.
Use a combination of QuickGraph (GitHub, CodePlex) and Graph# for WPF (GitHub fork, CodePlex) - both top notch libraries. They work really well for me but the documentation for Graph# is almost non-existant.
We've used ZedGraph which is an Open Source project written in C#, so you can tweak it if you feel it is necessary. It served our needs which sound like they're very close to what you described. There's even a wiki site for the project with some pretty good samples.
I am working in the NDepend team and we switched from GraphViz to MsAgl (Microsoft Automatic Graph Layout) in september 2008. The MsAgl license allows commercial utilisation. Here are a few sample pictures of MsAgl graphs integrated in NDepend (everything is interactive, nodes are movable/selectable/removable/clickable, edges are editable/selectable/removable/clickable, the layout is zoomable, and also, while it could be cleaner the MsAgl API is clean enough to work with):
Though my previous post get deleted I'll try to give more complex answer on the question.
The topmost answer is not quite actual anymore as the Graph# library is strongly outdated.
I'll recommend to check the combination of GraphX and Quickgraph. GraphX as the rendering engine and Quickgraph as the graph management and math operation component.
GraphX library is coded for WPF 4.0 and METRO. It provides many features that Graph# lacks:
Improved rendering performance for large graphs
Edge routing and bundling support, many other edge options
Enhanced zoom control which supports Overview window and multiple vertices selection
Rich documentation and samples
Also GraphX supports all the original layout algorithms from Graph#.