Konstantin,

I have a question about your "splitting the plane into cells":
Are you assuming there is an obvious embedding from the planar graph metric into the euclidean plane first? When you talk of cells of size "delta x delta" I understand that you have the points of the original metric somehow laid out on a rectangular grid, then partition the points into squares on that grid. But you don't mean to look at the diameter of components of that partition in the original "shortest path" metric. Is that a correct understanding?