在数学上,一个图是表示物体之间关系的抽象结构。图是由一个顶点集合和连接这些顶点的直线或者曲线组成的。图是一种自然的结构,在许多科学领域扮演非常重要的角色,例如,有限元分析、海量数据点网格分析。图也常常用来对许多工程问题建模。比如对社会关系网进行建模、网络交换机之间的路由和通信建模、无线网格节点建模、高层计算机视觉对象间关系、城市间的航空线路等。图这种结构广泛存在于各个领域,因此将图的抽象结构可视化将有助于更好地理解对象间的关系。图的曲面嵌入根据亏格的不同可以给出图在球面、欧氏和双曲空间中无边交叉的实现,对于亏格为0的图,可以将其嵌入到球面空间；对于亏格为1的图,可以将其嵌入到圆环面；对于亏格大于1的图,我们将其覆盖空间嵌入到双曲圆盘中。这种对图的量化,也是对于抽象关系的一种量化,有着非常广的应用价值。图的嵌入问题在计算机科学领域有着非常根本的重要性。众所周知,计算图的一个最小亏格的嵌入曲面是NP-Hard问题。受到代数拓扑的启发,我们发明了一个算法,可以高效单调的减少图嵌入曲面的亏格,并可寻找到称为拟平面图的拓扑曲面。此外,通过使用最前沿的几何工具,比如里奇曲率流(用来证明庞加莱猜想的数学工具),我们可以将普通的图嵌入到正则黎曼度量的曲面上。这种方法是现今解决图的嵌入这一难点问题最好的方法之一。基于以上研究问题,本文的工作主要围绕三个方面展开讨论：1)图的拓扑曲面嵌入；2)计算图的单值化度量和空间嵌入；3)图的曲面嵌入在无线传感器网络上的应用。本文就这几个问题的解决给出了新的理论和算法,具体的研究工作和成果包括：1、拓扑图理论及图的亏格提出一种启发式算法计算图的亏格,通过计算找到接近于图的较小亏格。对于给定的无向图,为每个顶点上的边给定一个圆排列,就得到该图在此给定圆排列下的一个封闭二流形。此二流形的亏格就是图在该圆排列下的亏格。如何得到此图的一个亏格最小的圆排列被证明是NP-hard。此算法可以高效单调的降低图的亏格。该算法可以有效的降低图的拓扑复杂度,由于许多在图上进行的拓扑计算方法的复杂度与图的嵌入亏格数有关,所以较低的亏格可以降低这些算法的复杂度。2、图的度量及其曲面嵌入在由图得到的二流形上,进行三角剖分从而得到三角网格。对于亏格小于2的网格使用欧氏的离散离奇曲率流计算欧氏度量,对于亏格等于2或者大于2的图使用双曲离奇曲率流计算双曲度量。最终由图得到的二流形成为了度量空间。在得到的度量下,图所形成的2流形上的每个面都是凸多边形。对于亏格为0的图,使用得到的欧氏度,最终将图嵌入到球面。对于亏格为1的图,使用得到的欧氏度量,最终将图嵌入到圆环面。对于亏格大于或者等于2的图,使用计算所得的双曲度量,最终将图的覆盖空间嵌入到双曲圆盘中。通过该算法,我们首次得到了图的嵌入曲面的单值化度量,在该度量下图的高斯曲率处处相等。这种图的几何可以大大降低图的可视化难度,使我们无边交叉的将图绘制到相应的空间中。3、图的曲面嵌入在无线传感器网络上的应用对于由无线传感器网络所形成的平面图,赋予欧氏度量,在复平面通过优化一个莫比乌斯变换,并将平面图嵌入到上半球面。网络在上半球面上使用球面度量,可以进行高效的贪婪路由。通过恰当的选取复平面的莫比乌斯变换,可以改变贪婪路由算法的路径,从而避开使用频率高的无线节点,平衡网络负载。对于分布在管道中的无线传感器网络,我们使用可变尺度的方法在三维空间中进行路由。首先将网络所形成的图进行降低亏格处理,然后算出高亏格图的双曲度量。在该度量下对网络进行Pants Decomposition。从而在Pants形成的邻接图上和Pants内部都可以进行信息的层次化路由,且可以保证信息的送达。我们使用图的整体几何的方法来解决无线传感器网络中重要的路由问题,这种全局的方法对于问题的解决是高效的。我们使用拓扑的方法得到图的较小亏格的拓扑曲面,并且该图的拓扑曲面是拟平面图。在此拓扑曲面上,通过适当的三角剖分,我们使用里奇流工具得到图的单值化度量,该度量下图的高斯曲率处处相等。这使我们可以将图嵌入到球面、圆环面和双曲圆盘这三种正则空间中。我们使用图的曲面嵌入这种整体几何的方法来解决无线传感器网络中的路由问题。图的曲面嵌入在很多领域必将有更多的重要应用。