Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations

Chan, Timothy M. and Hoffmann, Hella-Franziska and Kiazyk, Stephen and Lubiw, Anna (2013) Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 376-387 (Official URL:

Full text not available from this repository.


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(n√logn) approximation for paths and matchings, and an O(n) approximation for general graphs.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
ID Code:1390

Repository Staff Only: item control page


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)completeness. Discrete Appl. Math. 52(3), 233–252 (1994)

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., Spcompleteness. Discrete Appl. Math. 52(3), 233–252 (1994)oerhase, 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)