Using the linux kernel repository as the basis for improvements, there appears to be areas in history where there are so many branches that viewing all of them is semi-pointless as it'd take a giganto hi-res screen to fit them all in.
Instead draw elipses with a branch count number. The branches being merged/forked/committed to should always be draw completely however.
It should only do elipses in the case that drawing will not fit in the current column size, or the graph column would take up more than about 1/6 of the table widget size. A branch that is not drawn in the current cell but drawn previously (because of a branch, commit, or merge) should have an arrow in the appropriate direction signifying it still exists, its just not being drawn.
This way, important graph information/eye candy is there while eliminating super wide graph drawings. Probably speeds up drawing significantly as well making caching the images not necessary.
Git view does something similiar.