Graph Embeddings Motivated by Greedy Routing

VCLA hosted a talk by Roman Prutkin

ABSTRACT

In this talk, I shall present results on two problems from graph theory and computational geometry related to greedy routing on geometrically embedded graphs.

A Euclidean greedy embedding (or drawing) of a graph is a mapping of its vertices to points in the Euclidean plane, such that for every source-destination pair of vertices s,t there is always a neighbor u of s that is closer to t with respect to Euclidean distance. In this way, greedy routing on a greedy drawing never gets stuck in a local minimum. No complete characterization of graphs admitting Euclidean greedy drawings is known, although the existence has been proved for certain graph classes such as 3-connected planar graphs. In this talk, I present a characterization of all the trees admitting a greedy embedding in the Euclidean plane.

A greedily routable region (GRR) is a closed region in the plane, in which every destination point can be reached from every starting point by choosing the direction with maximum reduction of the distance to the destination in each point of the path (i.e., by moving greedily towards the destination). Partitioning a polygonal region into a small number of GRRs is used in a routing algorithm proposed for wireless sensor networks. The corresponding minimization problem is known to be NP-hard in general. I consider minimum GRR decomposition for hole-free polygons and plane straight-line drawings of graphs, which is a natural adjustment of the minimum GRR partition problem. For different variants of this problem, I either present optimal or approximate polynomial-time solutions or show NP-completeness.

The talk is based on joint work with Martin Nöllenburg and Ignaz Rutter.