度量是分析学中的基本概念, 同时也是图论比较核心的研究对象。度量空间的嵌入在运筹学、理论化学、计算机科学等许多领域的算法设计和分析方面是一个重要的要素。本项目主要研究图的度量空间在l1-空间中的等距离嵌入和扭曲嵌入的相关问题: 一探寻两个非二部的l1-图通过粘贴一条边后所得新图仍是l1-图的条件; 研究图G的线图L(G)的l1-嵌入性, 找出G与L(G)都是l1-嵌入的图; 二研究用禁止等距离子图来刻画l1-图的结构; 三研究圆柱面上的四边形镶嵌图的l1-嵌入性; 并研究圆柱面(莫比乌斯带)上的四(或六)边形镶嵌图的l1-嵌入的扭曲度; 四研究曲面图的共振图的超立方体嵌入及median性。该项目将图论与分析学, 几何学, 拓扑学, 代数学等很好的结合起来。本项目将进一步丰富和发展图的l1-嵌入的理论, 相关离散度量空间l1-嵌入的结果有助于分析学中的度量空间嵌入方面的研究。

Metric is a basic concept in analysis and it is in the core of the research in graph theory. Metric embeddings is a useful ingredient in the design and analysis of algorithms in operational research, theoretical chemestry, computer science, and so on. The project mainly study the isometric embeddings and distortion of graphic metric space into l1-space. It concerns the following problems: firstly, explore the condition of l1-embeddability of the graph obtained by gluing two non-bipartite l1-graphs along an edge; study the l1-embeddability of the line graph L(G) of a graph G, find out the graphs such that both G and L(G) are l1-embeddable; secondly, find forbidden isometric subgraphs to characterize the structure of l1-graphs; thirdly, study the l1-embeddability of quadrilateral tiling graphs embedded in cylinder, and study the distortion of l1-embeddings of quadrilateral (or hexagonal) tiling graphs embedded in a cylinder(or Mobius strip) ; fourthly, study the hypercube embedding and median of resonance graph of graphs embedded in a surface. The project combines graph theory with analysis, geometry, topology, algebra, etc. This study aims to further enrich and develop the l1-embeddable theories of graph, and the results of embeddings of discrete metric space are helpful to the research of graphic metric space embedding in analytical science.