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

路由是网络中最重要的算法问题之一。传统的路由是通过路由协议构造路由表来实现的。这样的解决方案空间效率低，并且需要相当大的设置开销，这使得它在某些网络（如无线传感器网络）中不可行。最近，几何路由被提出作为一种替代方法。几何路由通常使用节点的虚坐标来计算路由路径。通过在顶点上运行图形绘制算法来计算顶点的虚拟坐标。最简单的几何路由是贪婪路由，在这种路由中，顶点只是将消息转发给离目的地更近的邻居。贪心路由的第一个问题是它的理论适用性。为了使贪婪路由总是成功，对于网络中的每一对顶点u和v，必须有一条从u到v的距离递减的路径。不幸的是，并不是每个图都可以画得使得每一对顶点之间都存在距离递减的路径。贪心路由的第二个问题是它的实际可行性：贪心图中的虚坐标必须简洁。这两个问题的结合是贪心路由应用的一个重要障碍。本项目的目的是通过引入和研究一种新的图形绘制概念来解决这些贪婪路由问题：k几何嵌入，其中网络的每个节点可以映射到目标度量空间中的多达k个虚拟位置。对于网络中的两个节点u和v，将其所有虚拟位置之间的最小距离定义为这两个节点的距离。特别地，本项目将研究k贪心绘图，它被定义为k几何嵌入，其中总是存在距离递减路径。本研究的思想价值主要体现在：(1)新概念开辟了图形绘制的新领域，加强了图形绘制与网络路由的联系；（ii）所发展的理论将使贪心路由在更多种类的网络中可行。因此，贪婪路由可能成为一种真正实用的选择。本研究的广泛影响包括：(1)本研究的结果将对图论、图绘制和几何路由，特别是贪婪路由产生影响；（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.