It's a great chart, but DW-NOMINATE just measures how much distance there was between the positions (voting records) of the different parties. It doesn't measure what those positions meant in ideological terms.
Well DW-NOMINATE measures how much members of Congress vote together, but the results can be broken down into 2 dimensions, the weightier one being the first dimension, which they say "can be interpreted in most periods as government intervention in the economy or liberal-conservative in the modern era." And it turns out that the Democrats have pretty much always been on the left, hence why the xkcd graphic groups them consistently under "left-leaning parties."
Maybe this is a clearer graphic to demonstrate that, although it only goes back to 1879: http://voteview.com/images/House_and_Senate_Means_1879-2012_1.jpg
The Democrats were not in favor of greater government intervention in the economy in most of the nineteenth century, as they have been in most of the 20th and 21st. The Democrats are placed on the left mainly for convenience. There is continuity in voting patterns from one Congress to the next, but it does not mean the ideology is consistent over several generations. The fact that Farmer-Labor is placed on the right should suggest that the right-left distinction implied by the chart can't be taken at face value.