On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs
Subhas Kumar Ghosh and Koushik Sinha
Abstract
In the context of geographic routing, Papadimitriou and Ratajczak
conjectured that every 3-connected planar graph has a greedy embedding
(possibly planar and convex) in the Euclidean plane. Recently, greedy
embedding conjecture has been resolved, though the construction do not
result in a drawing that is planar and convex. In this work we consider
the planar convex greedy embedding conjecture and make some progress. We
show that in planar convex greedy embedding of a graph, weight of the
maximum weight spanning tree (T) and weight of the minimum weight
spanning tree (MST) satisfies WT(T)/WT(MST) <= (|V|-1)^{1-delta}, for
some $0 < delta <= 1. In order to present this result we define a notion
of weak greedy embedding. For beta >= 1 a beta-weak greedy embedding of
a graph is a planar embedding such that local optima is bounded by beta.
We also show that any three connected planar graph has a beta-weak
greedy planar convex embedding in the Euclidean plane with beta in
[1,2 sqrt{2} d(G)], where d(G) is the ratio of maximum and minimum
distance between pair of vertices in the embedding of G, and this bound
is tight.