Logo der Fakultät Logo LG Theoretische Informatik
 

Veröffentlichung

Titel:

On Monotone Drawings of Trees

AutorInnen: Philipp Kindermann
André Schulz
Joachim Spoerhase
Alexander Wolff
Kategorie: Konferenzbandbeiträge
erschienen in: Proceedings of the 23rd International Symposium on Graph Drawing (GD'14), pp. 488-500
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(n1.5)×O(n1.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.

Download: Proceeding Website
BibTeX-Eintrag: @InProceedings{kssw-omdot-gd14, Title = {On Monotone Drawings of Trees}, Author = {Philipp Kindermann and Andr{\'{e}} Schulz and Joachim Spoerhase and Alexander Wolff}, Booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing (GD'14)}, Year = {2014}, Editor = {Christian A. Duncan and Antonios Symvonis}, Pages = {488--500}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {8871}, Abstract = {A crossing-free straight-line drawing of a graph is \emph{monotone} if there is a monotone path between any pair of vertices with respect to \emph{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 \emph{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 \emph{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.}, Doi = {10.1007/978-3-662-45803-7_41} }
Philipp Kindermann | 22.11.2016
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen