Optimal stochastic planarization

Details Optimal stochastic planarization Optimal stochastic planarization

2010-04-10

arxiv.org/abs/1004.1666v2

Computer Science

Computational Geometry

Scientific paper

It has been shown by Indyk and Sidiropoulos [IS07] that any graph of genus g>0 can be stochastically embedded into a distribution over planar graphs with distortion 2^O(g). This bound was later improved to O(g^2) by Borradaile, Lee and Sidiropoulos [BLS09]. We give an embedding with distortion O(log g), which is asymptotically optimal. Apart from the improved distortion, another advantage of our embedding is that it can be computed in polynomial time. In contrast, the algorithm of [BLS09] requires solving an NP-hard problem. Our result implies in particular a reduction for a large class of geometric optimization problems from instances on genus-g graphs, to corresponding ones on planar graphs, with a O(log g) loss factor in the approximation guarantee.

Affiliated with

Also associated with

No associations

Rating

Optimal stochastic planarization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal stochastic planarization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal stochastic planarization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-600170