The Utility of Untangling

Dujmović, Vida (2015) The Utility of Untangling. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 321-332 (Official URL:

Full text not available from this repository.


In this paper we show how techniques developed for untangling planar graphs by Bose et al. [Discrete & Computational Geometry 42(4): 570–585 (2009)] and Goaoc et al. [Discrete & Computational Geometry 42(4): 542–569 (2009)] imply new results about some recent graph drawing models. These include column planarity, universal point subsets, and partial simultaneous geometric embeddings (with or without mappings). Some of these results answer open problems posed in previous papers.

Item Type:Conference Paper
Classifications:M Methods > M.600 Planar
P Styles > P.540 Planar
P Styles > P.999 Others
ID Code:1499

Repository Staff Only: item control page


Abellanas, M., Hurtado, F., Ramos, P.: Tolerancia de arreglos de segmentos. In: Proceedings of VI Encuentros de Geometría Computacional, pp. 77–84 (1995)

Angelini, P., Binucci, C., Evans, W., Hurtado, F., Liotta, G., Mchedlidze, T., Meijer, H., Okamoto, Y.: Universal point subsets for planar graphs. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 423–432. Springer, Heidelberg (2012)

Angelini, P., Evans, W., Frati, F., Gudmundsson, J.: SEFE with no mapping via large induced outerplane graphs in plane graphs. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 185–195. Springer, Heidelberg (2013)

Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric simultaneous embedding. J. Graph Algorithms Appl. 16(1), 37–83 (2012)

Bannister, M.J., Cheng, Z., Devanny, W.E., Eppstein, D.: Superpatterns and universal point sets. J. Graph Algorithms Appl. 18(2), 177–209 (2014)

Barba, L., Hoffmann, M., Kusters, V.: Column planarity and partial simultaneous geometric embedding for outerplanar graphs. In: Abstracts of the 31st European Workshop on Computational Geometry (EuroCG), pp. 53–56 (2015)

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualizationpp, pp. 349–381. CRC Press, Boca Raton (2013)

Bose, P.: On embedding an outer-planar graph in a point set. Comput. Geom. 23(3), 303–312 (2002)

Bose, P., Dujmović, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.R.: A polynomial bound for untangling geometric planar graphs. Discrete Comput. Geom. 42(4), 570–585 (2009)

Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 243–255. Springer, Heidelberg (2003)

Cano, J., Tóth, C.D., Urrutia, J.: Upper bound constructions for untangling planar geometric graphs. SIAM J. Discrete Math. 28(4), 1935–1943 (2014)

Cardinal, J., Hoffmann, M., Kusters, V.: On universal point sets for planar graphs. In: Akiyama, J., Kano, M., Sakai, T. (eds.) TJJCCGG 2012. LNCS, vol. 8296, pp. 30–41. Springer, Heidelberg (2013)

Castañeda, N., Urrutia, J.: Straight line embeddings of planar graphs on point sets. In: Proceedings of the 8th Canadian Conference on Computational Geometry, (CCCG), pp. 312–318 (1996)

Cibulka, J.: Untangling polygons and graphs. Discrete Comput. Geom. 43(2), 402–411 (2010)

Di Giacomo, E., Didimo, W., van Kreveld, M.J., Liotta, G., Speckmann, B.: Matched drawings of planar graphs. J. Graph Algorithms Appl. 13(3), 423–445 (2009)

Di Giacomo, E., Liotta, G., Mchedlidze, T.: How many vertex locations can be arbitrarily chosen when drawing planar graphs? CoRR abs/1212.0804 (2012)

Di Giacomo, E., Liotta, G., Mchedlidze, T.: Lower and upper bounds for long induced paths in 3-connected planar graphs. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 213–224. Springer, Heidelberg (2013)

Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 2(51), 161–166 (1950)

Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Mathematica 2, 463–470 (1935)

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. Comput. Geom. 42(6–7), 704–721 (2009)

Evans, W., Kusters, V., Saumell, M., Speckmann, B.: Column planarity and partial simultaneous geometric embedding. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 259–271. Springer, Heidelberg (2014)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting fary embeddings of planar graphs. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, pp. 426–433 (1988)

Goaoc, X., Kratochvíl, J., Okamoto, Y., Shin, C., Spillner, A., Wolff, A.: Untangling a planar graph. Discrete Comput. Geom. 42(4), 542–569 (2009)

Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points (solution to problem e3341). Am. Math. Monthly 98, 165–166 (1991)

Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Untangling planar graphs from a specified vertex position - hard cases. Discrete Appl. Math. 159(8), 789–799 (2011)

Kurowski, M.: A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs. Inf. Process. Lett. 92(2), 95–98 (2004)

Pach, J., Tardos, G.: Untangling a polygon. Discrete Comput. Geom. 28(4), 585–592 (2002)

Ramos, P.: Tolerancia de estructuras geométricas y combinatorias. Ph.D. thesis, Universidad Politécnica de Madrid, Madrid, Spain (1995)

Ravsky, A., Verbitsky, O.: On collinear sets in straight-line drawings. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 295–306. Springer, Heidelberg (2011)

Steele, J.M.: Variations on the monotone subsequence theme of Erdös and Szekeres. In: Aldous, D., Diaconis, P., Spencer, J., Steele, J.M. (eds.) Discrete probability and algorithms, pp. 111–131. Springer, Heidelberg (1995)