Monotone Drawings of Graphs

Angelini, Patrizio and Colasante, Enrico and Di Battista, Giuseppe and Frati, Fabrizio and Patrignani, Maurizio (2011) Monotone Drawings of Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 13-24 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_2).

Full text not available from this repository.

Abstract

We study a new standard for visualizing graphs: A monotone drawing is a straight-line drawing such that, for every pair of vertices, there exists a path that monotonically increases with respect to some direction. We show algorithms for constructing monotone planar drawings of trees and biconnected planar graphs, we study the interplay between monotonicity, planarity, and convexity, and we outline a number of open problems and future research directions.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_2
Classifications:G Algorithms and Complexity > G.560 Geometry
P Styles > P.540 Planar
ID Code:1188

Repository Staff Only: item control page

References

Angelini, P., Colasante, E., di Battista, G., Frati, F., Patrignani, M.: Monotone drawings of graphs. Tech. Report 178, Dip. di Informatica e Automazione, Università Roma Tre (2010)

Angelini, P., Frati, F., Grilli, L.: An algorithm to construct greedy drawings of triangulations. J. Graph Alg. Appl. 14(1), 19–51 (2010)

Arkin, E.M., Connelly, R., Mitchell, J.S.: On monotone paths among obstacles with applications to planning assemblies. In: SoCG 1989, pp. 334–343 (1989)

Brocot, A.: Calcul des rouages par approximation, nouvelle methode. Revue Chronometrique 6, 186–194 (1860)

Carlson, J., Eppstein, D.: Trees with convex faces and optimal angles. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 77–88. Springer, Heidelberg (2007)

Chiba, N., Nishizeki, T.: Planar Graphs: Theory and Algorithms. In: Annals of Discrete Mathematics, vol. 32, North-Holland, Amsterdam (1988)

Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61, 175–198 (1988)

Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996)

Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comp. 25(5), 956–997 (1996)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comp. 31(2), 601–625 (2001)

Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)

Moitra, A., Leighton, T.: Some results on greedy embeddings in metric spaces. In: Foundations of Computer Science (FOCS 2008), pp. 337–346 (2008)

Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theoretical Computer Science 344(1), 3–14 (2005)

Stern, M.A.: Ueber eine zahlentheoretische funktion. Journal fur die reine und angewandte Mathematik 55, 193–220 (1858)