Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
On Monotone Drawings of Trees
verfasst von : Philipp Kindermann, André Schulz, Joachim Spoerhase, Alexander Wolff
Erschienen in: Graph Drawing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.