How to draw free trees inside bounded rectilinear polygons

Abstract

Drawing graphs on a 2D grid with prescribed size is NP-complete, even if we restrict ourselves to planar orthogonal grid drawings of trees. In this paper, we introduce a new algorithm for polyline drawing of free trees on 2D grids which are bounded by rectilinear polygons. Our algorithm uses straight skeleton and simulated annealing and aims to distribute the vertices of the given trees uniformly on the given bounded grids. Our experimental results show that our algorithm is relatively successful to achieve uniform distribution of the nodes of the given trees. To our knowledge, this paper is the first attempt to develop algorithms that draw trees on restricted 2D grids which are bounded by simple rectilinear polygons.

E-mail: [email protected]

Keywords:

• Computational geometry
• Graph drawing
• Straight skeleton
• Simulated annealing

Acknowledgement

This research was in part supported by a grant from I.P.M. (No. CS1383-4-1).

Notes

E-mail: [email protected]