On Monotone Drawings of Trees

Kindermann, Philipp and Schulz, André and Spoerhase, Joachim and Wolff, Alexander (2014) On Monotone Drawings of Trees. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 488-500 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_41).

Full text not available from this repository.

Abstract

A crossing-free straight-line drawing of a graph is monotone if there is a monotone path between any pair of vertices with respect to some direction. We show how to construct a monotone drawing of a tree with n vertices on an O(n 1.5) ×O(n 1.5) grid whose angles are close to the best possible angular resolution. Our drawings are convex, that is, if every edge to a leaf is substituted by a ray, the (unbounded) faces form convex regions. It is known that convex drawings are monotone and, in the case of trees, also crossing-free. A monotone drawing is strongly monotone if, for every pair of vertices, the direction that witnesses the monotonicity comes from the vector that connects the two vertices. We show that every tree admits a strongly monotone drawing. For biconnected outerplanar graphs, this is easy to see. On the other hand, we present a simply-connected graph that does not have a strongly monotone drawing in any embedding.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_41
Classifications:G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
ID Code:1457

Repository Staff Only: item control page

References

Alamdari, S., Chan, T.M., Grant, E., Lubiw, A., Pathak, V. Self-approaching graphs. In: Didimo, W., Patrignani, M. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 260-271

Angelini, P., Colasante, E., Battista, G.D., Frati, F., Patrignani, M. (2012) Monotone drawings of graphs. J. Graph Algorithms Appl. 16: pp. 5-35

Angelini, P., Didimo, W., Kobourov, S., Mchedlidze, T., Roselli, V., Symvonis, A., Wismath, S.: Monotone drawings of graphs with fixed embedding. To appear in Algorithmica, http://dx.doi.org/10.1007/s00453-013-9790-3

Arkin, E.M., Connelly, R., Mitchell, J.S.: On monotone paths among obstacles with applications to planning assemblies. In: Proc. 5th Ann. ACM Symp. Comput. Geom. (SoCG 1989), pp. 334–343 (1989)

Bárány, I., Rote, G. (2006) Strictly convex drawings of planar graphs. Doc. Math. 11: pp. 369-391

Carlson, J., Eppstein, D. Trees with convex faces and optimal angles. In: Kaufmann, M., Wagner, D. eds. (2007) Graph Drawing. Springer, Heidelberg, pp. 77-88

Dhandapani, R. (2010) Greedy drawings of triangulations. Discrete Comput. Geom. 43: pp. 375-392

Hardy, G., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press (1979)

Hossain, M.. I., Rahman, M.. S. Monotone Grid Drawings of Planar Graphs. In: Chen, J., Hopcroft, J.E., Wang, J. eds. (2014) Frontiers in Algorithmics. Springer, Heidelberg, pp. 105-116

Leighton, T., Moitra, A. (2010) Some results on greedy embeddings in metric spaces. Discrete Comput. Geom. 44: pp. 686-705

Nöllenburg, M., Prutkin, R. Euclidean greedy drawings of trees. In: Bodlaender, H.L., Italiano, G.F. eds. (2013) Algorithms – ESA 2013. Springer, Heidelberg, pp. 767-778