AF: Smal: k-Greedy Drawing of Graphs and Their Applications

路由是网络中最重要的算法问题之一。传统的路由是通过路由协议构建路由表来完成的。这样的解决方案是空间效率低的，它需要相当大的设置开销，这使得它不可行的一些网络，如无线传感器网络。最近，几何布线已被提出作为一种替代方法。几何布线通常使用节点的虚拟坐标来计算布线路径。通过在顶点上运行图形绘制算法来计算顶点的虚拟坐标。最简单的几何路由是贪婪路由，其中顶点简单地将消息转发到更接近目的地的邻居。贪婪路由的第一个问题是它的理论适用性。为了使贪婪路由总是成功，对于网络中的每一对顶点u和v，必须有一条从u到v的距离递减路径。不幸的是，不是每个图都能画出每一对顶点之间都存在距离递减路径。贪婪布线的第二个问题是它的实际可行性：贪婪绘图中的虚拟坐标必须简洁。这两个问题的结合是贪婪路由的适用性的一个重大障碍。该项目的目的是通过引入和研究一种新的图形绘制概念来解决这些贪婪路由问题：k-几何嵌入，其中网络的每个节点可以映射到目标度量空间中的k个虚拟位置。对于网络中的两个节点u和v，它们的所有虚拟位置之间的最小距离被定义为这两个节点的距离。特别是，本项目将研究k-greedy drawing，它被定义为一个k-几何嵌入，其中距离减少的路径总是存在的。这项研究的知识价值包括：（i）新的概念将打开一个新的领域的图形绘制和加强之间的联系图形绘制和网络路由;（ii）开发的理论将使贪婪路由可行的更多类型的网络。因此，贪婪路由可能成为真正实用的替代方案。这项研究的更广泛的影响包括：（i）从这项研究中获得的结果将对图论，图形绘制和几何路由，特别是贪婪路由产生影响;（ii）研究成果将被纳入计算机科学教育。

Routing is one of the most important algorithmic problems in networking. Traditional routing is done by constructing routing tables via routing protocols. Such a solution is space inefficient and it requires considerable setup overhead, which makes it infeasible for some networks such as wireless sensor networks. Recently, geometric routing has been proposed as an alternative approach. Geometric routing often uses virtual coordinates of the nodes to compute routing paths. The virtual coordinates of the vertices are computed by running graph drawing algorithms on them. The simplest geometric routing is greedy routing, in which a vertex simply forwards messages to a neighbor that is closer to the destination. The first problem for greedy routing is its theoretical applicability. In order for greedy routing to always succeed, for every pair of vertices u and v in the network, there must be a distance-decreasing path from u to v. Unfortunately, not every graph can be drawn so that distance-decreasing paths exist between every pair of vertices. The second problem for greedy routing is its practical feasibility: the virtual coordinates in a greedy drawing have to be succinct. The combination of the two problems is a significant hurdle for the applicability of greedy routing. The aim of this project is to tackle these greedy routing problems by introducing and studying a new notion of graph drawing: k-geometric embedding, in which each node of a network can be mapped into up to k virtual locations in the target metric space. For two nodes u and v in the network, the smallest distance among all their virtual locations is defined as the distance of these two nodes. In particular, this project will study k-greedy drawing, which is defined to be a k-geometric embedding in which distance-decreasing paths always exist.The intellectual merits of this research include the following: (i) the new concepts will open a new area of graph drawing and strengthen the connection between graph drawing and network routing; (ii) the theory developed will make greedy routing feasible for more kinds of networks. Consequently, greedy routing may become a truly practical alternative. The broader impacts of this research include the following: (i) the results obtained from this research will have impact on graph theory, graph drawing, and geometric routing, especially greedy routing; (ii) the research results will be incorporated into computer science education.