×

On monotone drawings of trees. (English) Zbl 1405.68249

Duncan, Christian (ed.) et al., Graph drawing. 22nd international symposium, GD 2014, Würzburg, Germany, September 24–26, 2014. Revised selected papers. Berlin: Springer (ISBN 978-3-662-45802-0/pbk). Lecture Notes in Computer Science 8871, 488-500 (2014).
Summary: 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}) \times 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.
For the entire collection see [Zbl 1302.68012].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv