Modern genotyping techniques are producing increasingly high numbers of genetic markers that can be scored in experimental populations of plants and animals. Ordering these markers to form a reliable linkage map is computationally challenging. There is a wide literature on this topic, but much has focussed on populations derived from diploid, homozygous parents. Here we explore the use of multidimensional scaling (MDS) to order markers from with a cross between autotetraploid parents, using simulated data and also experimental data from a potato population. We compare different functions of the recombination fraction and lod score to form the MDS stress function, and find that a lod2 weighting generally performs well, including when missing values and genotyping errors are present. We conclude that unconstrained MDS gives a rapid way to detect and remove problematic markers, and that both constrained MDS and principal curve analysis give reliable marker orders, with the latter approach being particularly rapid. This approach could also be applied to experimental populations of diploid species.