Optimal Stochastic Planarization

It has been shown by Indyk and Sidiropoulos 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. 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 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-p graphs, to corresponding ones on planar graphs, with a O(log g) loss factor in the approximation guarantee.

Authors

• Anastasios Sidiropoulos

Keywords

• Extraterrestrial measurements
• Polynomials
• Partitioning algorithms
• Minimization
• Generators
• Optimization
• Distortion
• Class Of Problems
• Planar Graphs
• Class Of Optimization Problems
• Minimum Distance
• Shortest Path
• Stochastic Embedding
• Random Tree
• Loop System
• Common Endpoint
• Finite Graph
• Fundamental Group
• Vertical Step
• embeddings
• genus