By multiplexed analysis of restriction-site associated DNA markers (RAD-seq) using the Illumina platform, hundreds of individuals can be rapidly and inexpensively genotyped. Unfortunately, available methods for constructing genetic maps do not support a very large number of markers and do not tolerate the high frequency of missing information at individual markers typical for RAD-seq. We present a method that can compute maps from tens of thousands of markers. The alleles in the cross are inferred using clustering of read data from the parental or F2-generation. Using a bootstrapping approach that is robust against genotyping errors and missing data, physically distant groups of markers that are close to each other are identified. Next, these groups of close markers are joined into linkage groups. On each linkage group, a subset of sufficiently distant markers is selected, and using a maximum likelihood model, pairwise distances are estimated. Marker order is defined by the shortest roundtrip that visits all markers. The reliability of this map is improved by comparing several near-optimal roundtrips using global rearrangements and local permutations. Only highly reliable markers are kept. Afterwards, density can be improved by placing additional markers into bins on the map. This method has been applied to compute genetic maps of two plants with eight chromosomes, Capsella rubella and Arabis alpina. The relationship of these maps to de novo assemblies from short read data will be presented: the map is used to orient contigs, and the contigs are used to verify sections of the map.