Strict Confluent Drawing

Eppstein, David and Holten, Danny and Löffler, Maarten and Nöllenburg, Martin and Speckmann, Bettina and Verbeek, Kevin (2013) Strict Confluent Drawing. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 352-363 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_31).

Full text not available from this repository.

Abstract

We define strict confluent drawing, a form of confluent drawing in which the existence of an edge is indicated by the presence of a smooth path through a system of arcs and junctions (without crossings), and in which such a path, if it exists, must be unique. We prove that it is NP-complete to determine whether a given graph has a strict confluent drawing but polynomial to determine whether it has an outerplanar strict confluent drawing with a fixed vertex ordering (a drawing within a disk, with the vertices placed in a given order on the boundary).

Item Type:Conference Paper
Classifications:P Styles > P.300 Curved
P Styles > P.540 Planar
ID Code:1388

Repository Staff Only: item control page

References

Bekos, M.A., Kaufmann, M., Kobourov, S.G., Symvonis, A.: Smooth orthogonal layouts. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 150–161. Springer, Heidelberg (2013)

Collins, C.R., Stephenson, K.: A circle packing algorithm. Comput. Geom. Theory Appl. 25(3), 233–256 (2003)

Cui, W., Zhou, H., Qu, H., Wong, P.C., Li, X.: Geometry-based edge clustering for graph visualization. IEEE TVCG 14(6), 1277–1284 (2008)

Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: Visualizing non-planar diagrams in a planar way. J. Graph. Algorithms Appl. 9(1), 31–52 (2005)

Dwyer, T., Marriott, K., Wybrow, M.: Integrating edge routing into force-directed layout. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 8–19. Springer, Heidelberg (2007)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Delta-confluent drawings. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 165–176. Springer, Heidelberg (2006)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. Algorithmica 47(4), 439–452 (2007)

Eppstein, D., Holten, D., Löffler, M., Nöllenburg, M., Speckmann, B., Verbeek, K.: Strict confluent drawing. CoRR, abs/1308.6824 (2013)

Eppstein, D., Simons, J.A.: Confluent hasse diagrams. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 2–13. Springer, Heidelberg (2011)

Hirsch, M., Meijer, H., Rappaport, D.: Biclique edge cover graphs and confluent drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 405–416. Springer, Heidelberg (2007)

Holten, D.: Hierarchical edge bundles: visualization of adjacency relations in hierarchical data. IEEE TVCG 12(5), 741–748 (2006)

Holten, D., van Wijk, J.J.: Force-Directed Edge Bundling for Graph Visualization. Computer Graphics Forum 28(3), 983–990 (2009)

Hui, P., Pelsmajer, M.J., Schaefer, M., Štefankovič, D.: Train tracks and confluent drawings. Algorithmica 47(4), 465–479 (2007)

Hurter, C., Ersoy, O., Telea, A.: Graph Bundling by Kernel Density Estimation. Computer Graphics Forum 31(3pt. 1), 865–874 (2012)

Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)

Mohar, B.: A polynomial time circle packing algorithm. Discrete Math. 117(1-3), 257–263 (1993)

Quercini, G., Ancona, M.: Confluent drawing algorithms using rectangular dualization. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 341–352. Springer, Heidelberg (2011)