Simple Compact Monotone Tree Drawings

08/31/2017
by   Anargyros Oikonomou, et al.
0

A monotone drawing of a graph G is a straight-line drawing of G such that every pair of vertices is connected by a path that is monotone with respect to some direction. Trees, as a special class of graphs, have been the focus of several papers and, recently, He and He showed how to produce a monotone drawing of an arbitrary n-vertex tree that is contained in a 12n × 12n grid. In this paper, we present a simple algorithm that constructs for each arbitrary tree a monotone drawing on a grid of size at most n × n.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset