<p>I need advice for rendering an undirected graph with 178,000 nodes and 500,000 edges.  I've tried Neato, Tulip, and Cytoscape.  Neato doesn't even come remotely close, and Tulip and Cytoscape claim they can handle it but don't seem to be able to.  (Tulip does nothing and Cytoscape claims to be working, and then just stops.)</p>

<p>I'd just like a vector format file (ps or pdf) with a remotely reasonable layout of the nodes.</p>

Mathematica could very likely handle it, but I have to admit my first reaction was along the lines of the comment that said "take a piece of paper and color it black." Is there no way to reduce the density of the graph?
A possible issue is that you seem to be looking for layout, not just rendering. I have no knowledge about the Big O characteristics of the layouts implemented by various tools, but intuitively I would guess that it might take a
long
time to lay out that much data.