Drawing Free Trees Inside Simple Polygons Using Polygon Skeleton

Abstract

Most of graph drawing algorithms draw graphs on unbounded planes. In this paper we introduce a new polyline grid drawing algorithm for drawing free trees on plane regions which are bounded by simple polygons. Our algorithm uses the simulated annealing (SA) method, and by means of the straight skeletons of the bounding polygons guides the SA method to uniformly distribute the vertices of the given trees over the given regions. Our results show improvements to the previous algorithms that use the SA method to draw graphs inside rectangles. To our knowledge, this paper is the first attempt for developing algorithms that draw graphs on regions which are bounded by simple polygons.