Abstract
It has been recently shown that any graph of genus g > 0 can be stochastically embedded into a distribution over planar graphs, with distortion O(log(g + 1)) [Sidiropoulos, FOCS 2010]. This embedding can be computed in polynomial time, provided that a drawing of the input graph into a genus-g surface is given.
We show how to compute the above embedding without having such a drawing. This implies a general reduction for solving problems on graphs of small genus, even when the drawing into a small genus surface is unknown. To the best of our knowledge, this is the first result of this type.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)
Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: 37th Annual Symposium on Foundations of Computer Science (Burlington, VT), pp. 184–193. IEEE Comput. Soc. Press, Los Alamitos (1996)
Borradaile, G., Lee, J.R., Sidiropoulos, A.: Randomly removing g handles at once. In: Proc. 25th Annual ACM Symposium on Computational Geometry (2009)
Chambers, E.W., Erickson, J., Nayyeri, A.: Homology flows, cohomology cuts. In: Proc. 41st Annual ACM Symposium on Theory of Computing (2009)
Chen, J., Kanchi, S.P., Kanevsky, A.: A note on approximating graph genus. Inf. Process. Lett. 61(6), 317–322 (1997)
Charikar, M., Sahai, A.: Dimension reduction in the ℓ1 norm. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 551–560. IEEE (2002)
Eppstein, D.: Dynamic generators of topologically embedded graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 599–608. Society for Industrial and Applied Mathematics (2003)
Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1038–1046. Society for Industrial and Applied Mathematics (2005)
Feige, U., Hajiaghayi, M.T., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629–657 (2008)
Kawarabayashi, K.I., Mohar, B., Reed, B.A.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: FOCS, pp. 771–780 (2008)
Indyk, P.: Tutorial: Algorithmic applications of low-distortion geometric embeddings. In: Symposium on Foundations of Computer Science (2001)
Indyk, P., Sidiropoulos, A.: Probabilistic embeddings of bounded genus graphs into planar graphs. In: Proc. 23rd Annual ACM Symposium on Computational Geometry (2007)
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36(2), 177–189 (1979)
Matoušek, J.: On embedding trees into uniformly convex Banach spaces. Isr. J. Math. 114, 221–237 (1999)
Matousek, J.: Lectures on Discrete Geometry. Springer (2002)
Mohar, B., Thomassen, C.: Graphs on Surfaces. John Hopkins (2001)
Sidiropoulos, A.: Optimal stochastic planarization. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 163–170. IEEE (2010)
Thomassen, C.: The graph genus problem is np-complete. J. Algorithms 10(4), 568–576 (1989)
Thomassen, C.: Triangulating a surface with a prescribed graph. J. Comb. Theory, Ser. B 57(2), 196–206 (1993)
Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM (JACM) 51(6), 993–1024 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Makarychev, Y., Sidiropoulos, A. (2012). Planarizing an Unknown Surface. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2012 2012. Lecture Notes in Computer Science, vol 7408. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32512-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-32512-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32511-3
Online ISBN: 978-3-642-32512-0
eBook Packages: Computer ScienceComputer Science (R0)