We have used a "two-way pseudo-testcross" mapping strategy in combination with the random amplified polymorphic DNA (RAPD) assay to construct two moderate density genetic linkage maps for species of Eucalyptus. In the cross between two heterozygous individuals many single-dose RAPD markers will be heterozygous in one parent, null in the other and therefore segregate 1:1 in their F1 progeny following a testcross configuration. Meiosis and gametic segregation in each individual can be directly and efficiently analyzed using RAPD markers. We screened 305 primers of arbitrary sequence, and selected 151 to amplify a total of 558 markers. These markers were grouped at LOD 5.0, theta = 0.25, resulting in the maternal Eucalyptus grandis map having a total of 240 markers into 14 linkage groups (1552 cM) and the paternal Eucalyptus urophylla map with 251 markers in 11 linkage groups (1101 cM) (n = 11 in Eucalyptus). Framework maps ordered with a likelihood support > or = 1000:1 were assembled covering 95% of the estimated genome size in both individuals. Characterization of genome complexity of a sample of 48 mapped random amplified polymorphic DNA (RAPD) markers indicate that 53% amplify from low copy regions. These are the first reported high coverage linkage maps for any species of Eucalyptus and among the first for any hardwood tree species. We propose the combined use of RAPD markers and the pseudo-testcross configuration as a general strategy for the construction of single individual genetic linkage maps in outbred forest trees as well as in any highly heterozygous sexually reproducing living organisms. A survey of the occurrence of RAPD markers in different individuals suggests that the pseudo-testcross/RAPD mapping strategy should also be efficient at the intraspecific level and increasingly so with crosses of genetically divergent individuals. The ability to quickly construct single-tree genetic linkage maps in any forest species opens the way for a shift from the paradigm of a species index map to the heterodox proposal of constructing several maps for individual trees of a population, therefore mitigating the problem of linkage equilibrium between marker and trait loci for the application of marker assisted strategies in tree breeding.