圖形常被用來表示在現實世界中的許多問題，在許多情況下，漂亮的圖形繪製能夠對圖形的本質有更多的洞察。如此，圖形的繪製就成為圖論中一項重要的研究領域。目前已有許多不同的圖形繪製的審美尺度被提出討論，而對稱性是近年所被提出的一項新的審美尺度，且已廣泛地被採用。
然而，判斷一個圖形是否具有對稱性已經被證明是一個NP-Complete問題。因此，許多研究進而在特殊圖形上探討對稱性的問題。本論文則是探討如何於蜂巢圖上求得最大對稱子圖，我們提出一種蜂巢圖的座標表示法，並提出一個能在(n2)的時間複雜度內找出最大對稱子圖的演算法，其中n為蜂巢圖中正六角形的個數。

Graphs are known to be useful for modeling various problems in the real world. In many cases, a pretty drawing often offers more insights into the natural of a graph. Therefore, Graph drawing has emerged as a research topic of great importance in graph theory. Various criteria on constructing pretty drawings of graphs have been discussed. Recently, another aesthetic criterion, namely symmetry, has received increasing attention and been used widely.
However, the problem of determining whether a given graph has symmetry is NP-complete for general graphs. For restricted classes of graphs, there are polynomial time algorithms for constructing symmetric drawings. In this thesis, we will discuss how to find the maximum symmetric subgraph in honeycomb graphs. We propose a way, called Honeycomb Coordinate Representation, to represent honeycomb graphs. We also propose an algorithm that can find the maximum symmetric subgraph in time (n2), where n is the number of hexagon in a honeycomb graph.

[1]A.Baiocchi, F.Sestini, Near-Optimality of Distributed Load-adaptive Dynamic-Channel Allocation Strategies for Cellular Mobile Networks, Wireless Networks, Vol.2, NO.2, 1996, 129–142.
[2]R.Balakrishnan, K.Ranganathan, A Textbook of Graph Theory, Spring, 1999.
[3]G.Battista, P.Eades, R.Tamassia, I.Tollis, Graph Drawing：Algorithms for Visualization of Graphs, Prentice Hall, New York, 1999.
[4]M.Bern, D.Eppstein, Optimal Mobius Transformations for Information Visualization and Meshing, WADS, Lecture Notes in Computer Science 2125, 14–25, Springer Verlag, 2001.
[5]M.S.Chen, K.G.Shin, D.D.Kandlur, Addressing, Routing & Broadcasting in Hexagonal Mesh Multiprocessors, IEEE Transactions on Computers, Vol.39, NO.1, 1990, 10–18.
[6]K.Chin, H.Yen, The Symmetry Number Problem for Trees, Information Processing Letters, Vol.79, 2001, 73–79.
[7]N.Christofides, Graph Theory–An Algorithmic Approach, Academic Press, New York, 1975.
[8]S.J.Cyvin and I.Gutman, Kekule Structures in Benzenoid Hydrocadbons, Lecture Note in Chemistry, Vol.46, 1988.
[9]H.de Fraysseix, An Heuristic for Graph Symmetry Detection, Graph Drawing, Lecture Notes in Computer Science 1731, 276–285, Springer Verlag, 1999.
[10]S.H.Hong, P.Eades, A.Quigley and S.H.Lee, Drawing Algorithms for Series-Parallel Digraphs in Two and Three Dimensions, Graph Drawing, Lecture Notes in Computer Science 1547, 198–209, Springer Verlag, 1998.
[11]S.Hong, P.Eades and S.H.Lee, An Algorithm for Finding Geometric Automorphisms in Planar Graphs, Algorithms and Computation, Lecture Notes in Computer Science 1533, 277–286, Springer Verlag, 1998.
[12]S.Hong, P.Eades and S.H.Lee, Drawing Series Parallel Digraphs Symmetrically, Computational Geometry: Theory and Application, Vol. 17, Issue 3–4, 2000, 165–188.
[13]S.H. Hong and P.Eades, An Algorithm for Finding Three Dimensional Symmetry in Series Parallel Digraphs, ISAAC, Lecture Notes in Computer Science 1969, 266–277, Springer Verlag, 2000.
[14]S.H Hong and P.Eades, An Algorithm for Finding Three Dimensional Symmetry in Trees, Graph Drawing , Lecture Notes in Computer Science 1984, 360–371, Springer Verlag, 2000.
[15]S.H. Hong, Drawing Graphs Symmetrically in Three Dimensions, Graph Drawing, Lecture Notes in Computer Science 2265, 189–204, Springer Verlag, 2002.
[16]J.Manning, M.Atallah, Fast Detection and Display of Symmetry in Trees, Congressus Numerantium, Vol.64, 1988, 159–169.
[17]J.Manning, Geometric Symmetry in Graphs, Ph.D. Dissertation, Department of Computer Science, Purdue University, West Lafayette, IN, 1990.
[18]J.Manning, M.J.Atallah, Fast Detection and Display of Symmetry in Outerplanar Graphs, Technical Report CSD-TR-606, Department of Computer Sciences, Purdue University, West Lafayette, IN, 1986.
[19]D.Milutinovic, V.Milutinovic, B.Soucek, The Honeycomb Architecture, Computer, Vol.20, NO.4, 1987, 81–83.
[20]P.P.Mitra, M.A.U.Abedin, M.A.Kashem, Algorithm for Solving the Symmetry Number Problem on Trees, Information Processing Letters, Vol.91, 2004, 163–169.
[21]B.Parhami, D.M.Kwai, A Unified Formulation of Honeycomb and Diamond Networks, IEEE Transactions on Parallel and Distributed Systems, Vol.12, NO.1, 2001, 74–80.
[22]F.Pertlik, The Distortion of Hexagonal Close Packing of Oxygen Atoms in Co(OH)2 Compared to Isotypic Brucite-Type Structures, Monatshefte fur Chemie, Vol.130, 1999, 1083–1088.
[23]H.Purchase, Which Aesthetic Has the Greatest Effect on Human Understanding?, Graph Drawing, Lecture Notes in Computer Science 1353, 248–259, Springer Verlag, 1998.
[24]E.M.Reingold, J.S.Tilfold, Tidier Drawings in Trees, IEEE Transactions on Software Engineering, Vol.7, 1981, 223–228.
[25]G.Shi, P.Tong, A New Model for IN-Plane Bucking Analysis of Honeycomb Cellular Structures, Computer Modeling and Simulation in Engineering, Vol.4, NO.1, 1999, 50–57.
[26]I.Stojmenovic, Honeycomb Networks: Topological Properties and Communication Algorithms, IEEE Transactions on Parallel and Distributed Systems, Vol.8, NO.10, 1997, 1036–1042.
[27]R.Tamassia, J.E.Goodman, J.O’Rourke (Eds.), CRC Handbook of Discrete and Computational Geometry, CRC Press, Rockville, MD, 1997.