I want to visualize a large (tens of thousands of nodes) tree-like structure. The graph is almost a hierarchical tree, with the difference that there can be a few extra edges (making it not strictly at tree anymore, potentially making algorythms crash)
What is the best way I can do this?
You might be looking for something like ArcTrees (PDF) or Treemaps with Link Overlays (PDF). For the latter, edge-bundled versions (PDF)have been explored as well. The combination of a space-filling base visualization of the tree and the extra edges being displayed as arcs or links on top of them really helps to show where the tree property breaks down and how many extra edges there are. So, if that is what you are looking for, I'd go with these.
Otherwise, you can always use a standard DAG layout - e.g., as produced by the Sugiyama framework. See this Wikipedia entry for more information on this option.