Edited by author 03-01-2007 11:30 PM
PLANAR GRAPH PARTITIONS: (Rao et al.)

I was wondering why _three_ BFS are needed in order to obtain delta-partition of a given planar graph. Apparently, plane can be split into cells of size delta x delta by only two types of lines: horizontal and vertical (they correspond in some sense to two BFS over our plane). Then why two BFS don't suffice for planar graphs?

Now it seems to me that two BFS _do_ suffice to delta-partition any planar graph. A reason for that is that from the inner BFS we can get K3,2 (not only K3,1), then we can extend it to K3,3 using the outer BFS.

Any opinions as to whether this is correct?

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?

Fjola,

I didn't mean any embedding of planar graphs into planes.

Simply, the "fact" that plane can be partitioned using only two BFS suggests that the same can be done for planar graphs.

The techniques you presented seem to suffice for this.

Embedding l2 into l1

It seems that random projections should yield constant distortion embeddings from l2 into l1. As a crude estimate, if x is a unit vector in l2^D and A is a d-by-D matrix of Gaussian random variables, then in expectation, Ax/d has norm about 0.8. Large deviation bounds or concentration of measure (and d=O(log n)) can then do the rest as in the JL lemma.

Does this seem plausible? Using Dvorestsky's theorem would probably be of the same flavor, but might give a lower-dimension embedding.

Hi class,
just wanted to mention that Lawrence was correct in pointing out that the distortion for embedding NEG metrics into L2 achieved in Lee's paper was
log n ^{3/4}, not log n ^{4/3}, which would've been inferior to the Bourgain embedding.

Also, remember--the proof technique we focused on, based on finding large well-separated sets in NEG metrics, only leads to an embedding preserving a single distance scale [tau, 2tau]. To get a low-distortion embedding one has to follow up with the technical machinery of the Gluing Lemma, which wasn't covered.

Webmaster Link Exchange - Free Web Link Exchange Directory. Where Webmasters go to trade links with other webmasters

ed hardy is one of the most popular brands. ed hardy clothes displays the brilliant work of Don ed hardy uk. He is a gifted painter, printmaker and tattoo artist. cheap ed hardy

Christian Louboutin Peep-Toe Fringe Boots A sculpted suede peep-toe balances out the swingy fringe on this high-fashion style. Self-covered heel
christian louboutin sale
christian louboutin shoes

qpmXLu

Paul Smith Shoes uk store,See

discount Paul Smith large range of

online,We have Paul Smith Shoes and Paul

Smith Shoes in all styles.