Abstract
We consider the problem of finding a planar embedding of a graph at fixed vertex locations that minimizes the total edge length. The problem is known to be NP-hard. We give polynomial time algorithms achieving an \(O(\sqrt{n} \log n)\) approximation for paths and matchings, and an O(n) approximation for general graphs.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17(4), 717–728 (2001)
Sam Loyd, J.: Sam Loyd’s Cyclopedia of 5000 Puzzles Tricks and Conundrums. Lamb Publishing Company (1914)
Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 202–221 (2010)
Liebling, T.M., Margot, F., Müller, D., Prodon, A., Stauffer, L.: Disjoint paths in the plane. ORSA Journal on Computing 7(1), 84–88 (1995)
Bastert, O., Fekete, S.P.: Geometric wire routing. Technical Report 332, Angewandte Mathematik und Informatik, Universität zu Köln (1996) (in German)
Papadopoulou, E.: k-pairs non-crossing shortest paths in a simple polygon. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol. 1178, pp. 305–314. Springer, Heidelberg (1996)
Erickson, J., Nayyeri, A.: Shortest non-crossing walks in the plane. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 297–308 (2011)
Polishchuk, V., Mitchell, J.S.: Touring convex bodies – a conic programming solution. In: Proceedings of the 17th Canadian Conference on Computational Geometry, pp. 290–293 (2005)
Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 473–482 (2003)
Patrignani, M.: On extending a partial straight-line drawing. International Journal of Foundations of Computer Science 17(5), 1061–1069 (2006)
Bespamyatnikh, S.: Computing homotopic shortest paths in the plane. Journal of Algorithms 49(2), 284–303 (2003)
Efrat, A., Kobourov, S.G., Lubiw, A.: Computing homotopic shortest paths efficiently. Computational Geometry 35(3), 162–172 (2006)
Duncan, C.A., Efrat, A., Kobourov, S.G., Wenk, C.: Drawing with fat edges. International Journal of Foundations of Computer Science 17(5), 1143–1164 (2006)
Mitchell, J.S., Polishchuk, V.: Thick non-crossing paths and minimum-cost flows in polygonal domains. In: Proceedings of the 23rd Annual Symposium on Computational Geometry (SoCG), pp. 56–65 (2007)
Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. Journal of Graph Algorithms and Applications 10(2), 353–363 (2006)
Dujmović, V., Evans, W.S., Lazard, S., Lenhart, W., Liotta, G., Rappaport, D., Wismath, S.K.: On point-sets that support planar graphs. Computational Geometry 46(1), 29–50 (2013)
Katz, B., Krug, M., Rutter, I., Wolff, A.: Manhattan-geodesic embedding of planar graphs. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 207–218. Springer, Heidelberg (2010)
Hwang, F., Weng, J.: The shortest network under a given topology. Journal of Algorithms 13(3), 468–488 (1992)
Winter, P.: Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs. Discrete Applied Mathematics 47(2), 187–206 (1993)
Fink, M., Haunert, J.-H., Mchedlidze, T., Spoerhase, J., Wolff, A.: Drawing graphs with vertices at specified positions and crossings at large angles. In: Rahman, M. S., Nakano, S.-i. (eds.) WALCOM 2012. LNCS, vol. 7157, pp. 186–197. Springer, Heidelberg (2012)
Hurtado, F., Tóth, C.: Plane geometric graph augmentation: A generic perspective. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 327–354. Springer, New York (2013)
Takahashi, J., Suzuki, H., Nishizeki, T.: Shortest noncrossing paths in plane graphs. Algorithmica 16(3), 339–357 (1996)
Kamousi, P., Chan, T.M., Suri, S.: Stochastic minimum spanning trees in Euclidean spaces. In: Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG), pp. 65–74 (2011)
Edelsbrunner, H., O’Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing 15(2), 341–363 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Chan, T.M., Hoffmann, HF., Kiazyk, S., Lubiw, A. (2013). Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations. In: Wismath, S., Wolff, A. (eds) Graph Drawing. GD 2013. Lecture Notes in Computer Science, vol 8242. Springer, Cham. https://doi.org/10.1007/978-3-319-03841-4_33
Download citation
DOI: https://doi.org/10.1007/978-3-319-03841-4_33
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03840-7
Online ISBN: 978-3-319-03841-4
eBook Packages: Computer ScienceComputer Science (R0)