Research On Graph Embedding On Surface And Applications

In mathematics, a graph is an abstract structure used to model the relationship between objects. Graph consists of a vertex set and lines or curves that connect the vertices in the vertex set. Graph is a natural structure, plays a fundamental roles in many scientific fields. For examples, finite elements analysis, mass data points mesh analysis. Graph is often employed to modeling engineering problems. For examples, to modeling social network, traffic between telecommunication switches, wireless sensor network, high level computer vision, the airline between cities. The structure of graph widely exists in many fields, so to visualize the abstract graph structure can help us to understand the relationship between objects better. Graph surface embedding can embed the graph on to sphere, Euclidean space and hyperbolic space without edge crossing respect to its genus. For the genus equals to zero,we embed the graph on the unit sphere,the genus is one, we can embed the graph on the torus, if the genus is larger than one, we embed the universal covering space of graph on to the hyperbolic disk. This graph evaluation is also an evaluation of abstract relationship. It is well known that computing the genus of graph is a NP-Hard problem. Inspired by the methods in algebraic topology, we invented an algorithm, which can efficiently reduce the genus, and we can find a quasi-planar graph embedding. Furthermore, by using the cutting edge geometric tools, especially Ricci curvature flow, which has been applied for the proof of Poincare's conjecture, we can embed the general graph on surfaces with canonical Riemannian metrics. This method is among the best methods to solve the difficult problem of graph embedding.Base on the above research problems, we will discuss three core problems in this article:1) The topological embedding of graph;2) Compute the uniformization Riemannian metric on the graph and embed the graph in the space without edge crossing;3) The application in the wireless sensor network using graph surface embedding. New theories and algorithms are presented in this article, the detail research works include:1. Topological graph theory and graph genus.We invent a heuristic algorithm to compute the genus of a given graph. By using this algorithm we can find a relatively small genus of graph. For a given undirected graph, we assign a cyclic permutation on each vertex, then we get a topological closed2-manifold of this graph. The genus of this2-manifold is the genus of the graph under the cyclic permutation of each vertex. To get a minimum genus manifold of the graph is well known as a NP-Hard problem. Our algorithm can monotonely reduce the genus. The algorithm can reduce the complexity of the topology of graph. Because the complexity of many algorithm of graph is close relative to the genus, a smaller genus can reduce these algorithms'complexity.2. The metric of graph and its surface embeddingOn the2-manifold of graph, we triangulate the topological surface to get the triangle mesh. For the graph with genus less than2, we use Euclidean Ricci Flow to compute the graph metric. We use hyperbolic Ricci Flow to compute the uniformization metric for any graph with genus larger and equals to2. As a result, the2-manifold of graph is a metric space. Under the metric, the faces of graph on the2-manifold are all convex polygon. If the graph is genus0, we can use the Euclidean metric to embed the graph on to the sphere. If the graph is genus1, we can map the graph on to the torus. If the graph's genus is larger than1, we can use the hyperbolic metric to embed the universal covering space of the graph onto the hyperbolic disk. This geometry of graph can reduce the difficulty of graph visualization and we can get the draw the graph without edge crossing.3. The applications in wireless sensor network using Graph surface embedding For the planar graph formed by wireless sensor network, we assign it a Euclidean metric and embed it in the complex plane, by optimizing a Mobius transformation, we can map the graph onto the sphere. We can use the efficient greedy routing with the spherical metric. By choosing suitable Mobius transformation, we can change the routing path to avoid passing through some overloaded nodes. For the sparse sensor nodes locate in the complicated tunnel, we can use the scalable method to route in3D space. First we reduce the topological surface of the network graph, and then by using hyperbolic Ricci Flow, we can get the hyperbolic metric of the graph. Under this metric, Pants decomposition can be carried out. The message can be delivered using two level routing scheme, high level is on the adjacency graph of pants'pieces, the low level is in the inside of each piece, and guarantee delivery. Using the global geometry method to solve the problem of routing in wireless sensor network, we get efficient algorithms of routing in different network topology. We employed the topological method to get a relatively smaller genus of graph embedding surface, and it is a quasi-planar. We triangulate the topological surface properly, then we can run the Ricci Flow on it. Finally, we get the uniformization metric on the graph, this metric induces a constant curvature on the graph2-manifold everywhere. We embedding the metric graph on to unit sphere, torus and hyperbolic disk respect to its genus. Using the graph surface embedding method, we have solved the routing problem in the wireless sensor network. The graph surface embedding must have more important applications in many fields.