Research on Distortion of Embedding Graph into Euclidean Space
Shuangshuang Zhang · 2021
Distortion describes how the natural metric on the graph differs from the induced metric from an embedding into a Euclidean space or other metric spaces. In this paper, we mainly explain two parts. In the first part, we focus on the problem of proving the existence of minimal-distortion embeddings. By definition, the distortion of a graph G concerning a given metric space X is defined to be the infi- mum of the distortions of all embeddings from G to X. However, we prove that for G finite and , there is always an embedding of G that realizes the distortion of G. In the second half, we summarize all studies of the distortion problems up to date. We studied kinds of typical embedded issues, such as the plane graph of o points, a tree and special graphics.