6
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Some Results On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs

Preprint

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

A greedy embedding of a graph $$G = (V,E)$$ into a metric space $$(X,d)$$ is a function $$x : V(G) \to X$$ such that in the embedding for every pair of non-adjacent vertices $$x(s), x(t)$$ there exists another vertex $$x(u)$$ adjacent to $$x(s)$$ which is closer to $$x(t)$$ than $$x(s)$$. This notion of greedy embedding was defined by Papadimitriou and Ratajczak (Theor. Comput. Sci. 2005), where authors 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 proved by Leighton and Moitra (FOCS 2008). However, their algorithm do not result in a drawing that is planar and convex for all 3-connected planar graph in the Euclidean plane. In this work we consider the planar convex greedy embedding conjecture and make some progress. We derive a new characterization of planar convex greedy embedding that given a 3-connected planar graph $$G = (V,E)$$, an embedding $$x: V \to \bbbr^2$$ of $$G$$ is a planar convex greedy embedding if and only if, in the embedding $$x$$, weight of the maximum weight spanning tree ($$T$$) and weight of the minimum weight spanning tree ($$\func{MST}$$) satisfies $$\WT(T)/\WT(\func{MST}) \leq (\card{V}-1)^{1 - \delta}$$, for some $$0 < \delta \leq 1$$.

### Author and article information

###### Journal
0905.3812