Paper:

# Drawing Algorithm for Fuzzy Graphs Using the Partition Tree

## Yasunori Shiono^{*}, Tadaaki Kirishima^{**}, Yoshinori Ueda^{*},

and Kensei Tsuchida^{*}

^{*}Faculty of Information Sciences and Arts, Toyo University, 2100 Kujirai, Kawagoe-shi, Saitama 350-8585, Japan

^{**}University College of Cornerstone Education, J. F. Oberlin University, 3758 Tokiwa-machi, Machida-shi, Tokyo 194-0294, Japan

Fuzzy graphs have been used frequently and effectively as a method for sociogram analysis. A fuzzy graph has the fundamental characteristic of being able to express a variety of relationships between nodes. The drawing of fuzzy graphs has been studied in computer-aided analysis systems with human interfaces and methods using genetic algorithms. However, computer-aided analysis systems with human interfaces do not provide for automatic drawing, while methods using genetic algorithms have the defect of requiring too much execution time for finding a locally optimum solution. To overcome these defects, we propose an algorithm for drawing intelligible and comprehensive fuzzy graphs using a partition tree. This method automatically draws the fuzzy graphwith nodes arranged on the intersections of a latticed space. Since nodes are optimally arranged on the latticed intersections and put together at a nearby position in accordance with the transition of clusters according to cluster levels in the partition tree, drawing the algorithm makes fuzzy relations easier to understand through fuzzy graph representation. Moreover, fuzzy graphs can be drawn faster than by conventional methods. This paper describes the algorithm and its verification by introducing a system implementing the method for displaying fuzzy graphs. Moreover, we have carried out a case study in which a questionnaire has been administered to students, allowing us to analyze human relations quantitatively using a method based on fuzzy theory. Human relations are represented as fuzzy graphs by our algorithm and analyzed using the fuzzy graph.

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.16, No.5, pp. 641-652, 2012.

- [1] K. Sugiyama, “Automatic Drawing Method of Graph and its application,” Corona Publishing Co., Ltd., 1993 (in Japanese).
- [2] K. Sugiyama, “Graph drawing and applications for software and knowledge engineers,” World Scientific, 2002.
- [3] S. Miyamoto, “Introduction to Cluster Analysis:Theory and Applications of Fuzzy Clustering,” Morikita-Shuppan, 1999 (in Japanese).
- [4] S. Nakano, “Planar Drawings of Plane Graphs,” IEICE Trans. on Information and Systems, Vol.E83-D, No.3, pp. 384-391, 2000.
- [5] K. Misue, “Anchored Map: Graph Drawing Technique to Support Network Mining,” IEICE Trans. on Information and Systems, Vol.E91-D, No.11, pp. 2599-2606, 2008.
- [6] T. Nishizeki, K. Miura, and M. S. Rahman, “Algorithms for Drawing Plane Graphs,” IEICE Transactions on Information and Systems, Vol.E87-D, No.2, pp. 281-289, 2004.
- [7] J. North and G. Woodhull, “Online Hierarchical Graph Drawing,” In Proc. of the 9th Int. Symposium on Graph Drawing, pp. 232-246, 2001.
- [8] M. S. Rahman, N. Egi, and T. Nishizeki, “No-Bend Orthogonal Drawings of Subdivisions of Planar Triconnected Cubic Graphs,” IEICE Trans. on Information and Systems, Vol.E88-D, No.1, pp. 23-30, 2005.
- [9] S. E. Schaeffer, “Graph Clustering,” Computer Science Review I, pp. 27-64, 2007.
- [10] J. Tolle and O. Niggemann, “Supporting Intrusion Detection by Graph Clustering and Graph Drawing,” In Proc. of Third Int. Workshop on Recent Advances in Intrusion Detection (RAID 2000), pp. 51-62, 2000.
- [11] S. Mathew and M. S. Sunitha, “Node connectivity and arc connectivity of a fuzzy graph,” Information Sciences, Vol.180, pp. 519-531, 2010.
- [12] P. Eades, “A Heuristic for graph drawing,” Congressus Numerantium, Vol.42, pp. 149-160, 1984.
- [13] T. Kamada (Ed.), “Visualizing Abstract Objects and Relations, A Constraint-Based Approach,” World Scientific Publishing Co. Inc., 1960.
- [14] K. Sugiyama, S. Tagawa, and M. Toda, “Methods for visual understanding of hierarchic system structures,” J. of IEEE Trans. on System, Vol.11, No.2, pp. 109-125, IEEE, 1981.
- [15] H. Yamashita, T. Takizawa, M. Namekawa, and A. Satoh, “Fuzzy Graph Analysis System for Sociometry on Latticed Display,” In Proc. of 6th Int. Fuzzy Systems Association World Congress, pp. 543-546, IFSA, 1995.
- [16] A. Satoh, H. Yamashita, H. Suda et al., “Fuzzy Graph Modelling and its Analysis System,” In Proc. of 13th MODSIM’97, pp. 907-912, 1992.
- [17] A. Satoh, H. Yamashita, H. Suda et al., “Fuzzy Graph Analysis System and its Application,” In Proc. of Int. of Artificial Intelligence and Soft Computing (ASC 2000), pp. 19-23, 2000.
- [18] A. Satoh, Y. Makino, H. YamashIta, H. Uesu, and H. Suda et al., “Fuzzy Graph Analysis System for Sociometry on Latticed Display,” In Proc. of Joint 9th IFSA World Congress and 20th NAFIPS Int. Conf., pp. 139-144, IFSA and NAFIPS, 2001.
- [19] Y. Ueda, I. Nomoto, M. Matsumoto, and A. Satoh, “An Automatic Drawing of a Fuzzy Graph,” In Proc. of 2001 IEEE Int. Fuzzy Systems Conf., pp. 457-460, 2001.
- [20] Y. Ueda, M. Namekawa, and A. Satoh, “Improvement of the convergence characteristics in GA with an inversion,” J. of Biomedical Fuzzy Systems Association, Vol.13, No.1 pp. 97-107, 2011 (in Japanese).
- [21] K. Shinkai, “Fuzzy Cluster Analysis and its Evaluation Method,” Biomedical Soft Computing and Human Sciences, Vol.13, No.2, pp. 3-9, 2008.
- [22] H. Uesu, “Structure Analysis of Fuzzy Node Fuzzy Graph and its Application,” Biomedical Soft Computing and Human Sciences, Vol.11, No.1, pp. 41-49, 2006.
- [23] J. L. Moreno, “The sociometry Reader,” The Free Press, 1960.