Optimal Monotone Drawings of Trees

Preprint English OPEN
He, Dayu; He, Xin;
  • Subject: Computer Science - Data Structures and Algorithms

A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists abpath P_{uw} in G that is monotone in some direction l_{uw}. (Namely, the order of the orthogonal projections of the vertices of P_{uw} on l_{uw... View more
  • References (18)
    18 references, page 1 of 2

    [1] P. Angelini, E. Colasante, G. Di Battista, F. Frati and M. Patrignani, Monotone Drawings of Graphs, J. of Graph Algorithms and Appl. vol. 16, no. 1, pp. 5-35, 2012.

    [2] P. Angelini, F. Frati and L. Grilli, An Algorithm to Construct Greedy Drawings of Triangulations, J. of Graph Algorithms and Appl. vol. 14, no. 1, pp. 19-51, 2010.

    [3] P. Angelini, W. Didimo, S. Kobourov, T. Mchedlidze, V. Roselli, A. Symvonis, and S. Wismath, Monotone Drawings of Graphs with Fixed Embedding, Algorithmica, DOI 10.1007/s00453-013- 9790-3, 2013.

    [4] E. M. Arkin, R. Connelly and J.S. Mitchell, On Monotone Paths among Obstacles with Applications to Planning Assemblies, SoCG '89, pp. 334-343, 1989.

    [5] A. Brocot, Calcul des Rouages par Approximation, Nouvelle Methode, Revue Chronometrique, vol 6. pp. 186-194, 1860.

    [6] G. Di Battista and R. Tamassia, Algorithms for Plane Representations of Acyclic Digraphs, Theor. Comput. Sci. vol. 61, pp. 175-198, 1988.

    [7] A. Garg and R. Tammassia, On the Computational Complexity of Upward and Rectilinear Planarity Testing, SIAM J. Comp. vol. 31 (2), pp. 601-625, 2001

    [8] G. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th Edition, Oxford University Press, 1989.

    [9] X. He and D. He, Compact Monotone Drawing of Trees, in Proceedings of COCOON 2015, LNCS 9198, pp. 457-468, 2015.

    [10] X. He and D. He, Monotone Drawing of 3-Connected Plane Graphs, in Proceedings of ESA 2015, LNCS 9294, pp. 729-741, 2015.

  • Related Organizations (2)
  • Metrics
Share - Bookmark