Subscribe Now Subscribe Today
Research Article

Drawing Free Tress Inside Convex Regions Using Polygon Skeleton

Alireza Bagheri and Mohammadreza Razzazi

Using Simulated Annealing (SA) method for drawing graphs has appeared in the literature. Using this method directly to draw graphs inside a convex polygon leaves considerable amount of edge crossing. This is partly because it does not consider geometrical properties of polygons. In this paper we introduce a new algorithm, which by using geometrical properties of polygons guides SA method, and achieves a drawing that has much fewer edge crossing than the drawings of the previous known algorithms.

Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

Alireza Bagheri and Mohammadreza Razzazi , 2002. Drawing Free Tress Inside Convex Regions Using Polygon Skeleton. Journal of Applied Sciences, 2: 17-23.

DOI: 10.3923/jas.2002.17.23


Aichholzer, O. and F. Aurenhammer, 1996. Straight skeletons for general polygonal figures in the plane. Proceedings of the 2nd Annual International Conference on Computing and Combinatorics, June 17-19, 1996, Springer-Verlag, London, UK., pp: 117-126.

Aichholzer, O., F. Aurenhammer, D. Albert and B. Gartner, 1995. Straight skeletons of simple polygons. Proceedings of the 4th International Symposia of LIESMARS, October 25-27, 1995, Wuhan, China, pp: 114-124.

Aichholzer, O., F. Aurenhammer, D. Albert and B. Gartner, 1995. A novel type of skeleton for polygons. J. Universal Comput. Sci., 1: 752-761.
Direct Link  |  

Behrens, D., E. Barke and R. Tolkehn, 1997. Design driven partitioning. Proceedings of the 2nd Asian and South Pacific Design Automation Conference, January 28-31, 1997, Chiba, Japan, pp: 49-55.

Bourke, P., 1988. Calculating the area and centroid of a polygon.

Brandenburg, F.J., 1997. Graph Clustering I: Cycles of Cliques. In: Graph Drawing, Di Battista, G. (Ed.). Springer-Verlag, Berlin, Heidelberg, ISBN: 978-3-540-63938-1, pp: 158-168.

Brandengburg, F.J. and A. Sen, 1999. Graph clustering II: Trees of cliques with size bounds. Proceedings of the Spring Conference on Computer Graphics, (SCCG`99), Springer-Verlag, pp: 1-9.

Chan, T.M., 1999. A near-linear area bound for drawing binary trees. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, January 17-19, 1999, Baltimore, Maryland, United States, pp: 161-168.

Chin, F., J. Snoeyink and C.A. Wang, 1995. Finding the Medical Axis of a Simple Polygon in Linear Time. In: Algorithms and Computation, Staples, J., P. Eades, N. Katoh and A. Moffat (Eds.). Springer-Verlag, Berlin, Hamburg, pp: 382-391.

Davidson, R. and D. Harel, 1996. Drawing graphs nicely using simulation annealing. ACM Trans. Graphics, 15: 301-331.
Direct Link  |  

Edachery, J., A. Sen and F.J. Brandenburg, 1999. Graph clustering distance-K cliques. Proc. Int. Symp. Graph Draw., 99: 98-106.

Edaes, P. and Q.W. Feng, 1996. Multilevel Visualization of Clustered Graphs. In: Graph Drawing, Stephen North (Ed.). LNCS. 1190, Springer-Verlag, Berlin, Heidelberg, ISBN: 978-3-540-62495-0, pp: 101-112.

Edaes, P., Q.W. Feng and H. Nagamichi, 1999. Drawing clustered graph on an orthogonal grid. J. Graph Algorithums Applivationsms, 3: 3-29.

Eppteain, D. and J. Erickson, 1998. Rasing roofs cryshing cylces and playing pool: Applications of a data structure for finding pairwise interactions. Proceedings of the 4th ACM Symposium on Commputational Geometry, (ACMSCG'98), Minneapopis, pp: 58-67.

Purchase, H.C., 1997. Which aesthetic has the greatest effect on human understanding?. Proceedings of the 5th International Symposium on Graph Drawing, LNCS. 1353, September 11-20, 1997, Springer-Verlag, London, UK., pp: 248-261.

Roxborough, T. and A. Sen, 1997. Graph Clustering Using Multiway Ratio Cut (Software Demonstration). In: Graph Drawing, Di Battista, G. (Ed.). LNCS. 1353, Springer-Verlag, Berlin, Heidelberg, ISBN: 978-3-540-63938-1, pp: 291-296.

Sablowski, R. and A. Frick, 1996. Automatic Graph Clustering. In: Graph Drawing, North, S. (Ed.). LNCS. 1190, Springer-Verlag, Berlin, Hamburg, pp: 396-291.

Tan, X., J. Tong, P. Tan, N. Park and F. Lombardi, 1997. An efficient multi-way algorithum for balanced partitioning of VLSI circuuits. Proceedings of the International Conference on Computer Design, October 12-15, 1997, IEEE Computer Society, Washington, DC. USA., pp: 608-.

©  2019 Science Alert. All Rights Reserved