HOME JOURNALS CONTACT

Journal of Applied Sciences

Year: 2002 | Volume: 2 | Issue: 1 | Page No.: 17-23
DOI: 10.3923/jas.2002.17.23
Drawing Free Tress Inside Convex Regions Using Polygon Skeleton
Alireza Bagheri and Mohammadreza Razzazi

Abstract: 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.

Fulltext PDF

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.

Keywords: polygon skeleton, simulated annealing and Graph drawing

REFERENCES
  • 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    

  • Bourke, P., 1988. Calculating the area and centroid of a polygon. http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/.

  • 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
    Direct Link    

  • 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    

  • 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
    Direct Link    

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

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

  • 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
    Direct Link    

  • 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-.

  • 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.

  • 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.

    • © Science Alert. All Rights Reserved