A dissimilarity $d$ on a set $X$ is said to be {\em Robinson} if there exists a total order, said {\em compatible}, on $X$ such that $x<y<z \implies d(x, z) \geq \max\{d(x, y), d(y, z)\}$.

Roughly speaking, $d$ is Robinson if the points of $X$ can be represented on a line {\it ie.}

Robinson dissimilarities generalize line distances.

In this paper, we define $k$-dimensional Robinson dissimilarities, which generalize the possibility, for a metric set $(X, d)$, to be embedded into a $k$-dimensional Euclidean space. This generalization is more flexible than the classical embedding and

we show that every dissimilarity on an $n$-set $X$ is $(\log n)$-dimensional Robinson. We give an $O(n^3)$ algorithm which builds such an embedding.

This algorithm is based on an incremental algorithm to recognize Robinson dissimilarities.