There are a number of options, with various pros and cons - you may want to sift through this which is a list of software that does, more or less, what you're looking for.
Basically, there doesn't seem to be a free, pure C# implementation that is intended to be used in capacity of layout engine library. The closest thing seems to be MSAGL, which is downloadable if you're on MSDN, but otherwise is fairly pricey.
The distinction between Graph# and QuickGraph is that the latter provides graph traversal and manipulation primitives but does not provide any layout algorithms. Graph# has all the source available, and from what I've (briefly) looked at, has a neat separation between layout engine and drawing implementation.
Graphviz is written in pure C/C++ and is fairly monolithic, taking as input a text file describing the graph and producing various types of output, both vector and raster based. It isn't a great fit as a plug-in layout engine, but could be used by shelling out and providing the requisite input file and parsing the output. Not a very clean solution though.
There's also something called OGDF. Although it's written entirely in C++, it has been designed to be used as a layout engine library and has a well-structured interface for this. It supports various layout algorithms including optimised Sugiyama if that's what you're interested in.
If you're interested in implementing an optimised variation on Sugiyama, you could always roll your own using a neat description of the algorithm :)
Ultimately though, you should probably decide what type of layout you're after before you make a decision on the library.