在一個圖形中，若一個點v的鄰居所形成的誘導子圖是一個完全子圖的話，則v被稱作Simplicial。如果點v的鄰居所形成的誘導子圖是兩個完全子圖的聯集，則v被稱作Bisimplicial。在本論文中，我們研究一些具有Bisimplicial點性質的圖形。根據這個性質，我們可以為這些圖形建造出一個Bisimplicial序列。在此論文中，我們提出了一個O(n^4)的演算法在一般圖上判斷該圖是否存在一個Bisimplicial序列，同時我們也提出一個O(n^2)的演算法來判斷一個補圖是否具有這個序列。

A vertex v is called simplicial (respectively, bisimplicial) if the subgraph induced by N(v) is a clique (respectively, the union of two cliques). We investigate the class of graphs defined by the property that every induced subgraph has a vertex which is bisimplicial. By using this property, we propose algorithms for constructing bisimplicial elimination ordering on general graphs and cographs in O(n^4) and O(n^2) respectively.

Abstract i
Contents ii
List of Figures iii
1 Introduction 1
2 Algorithm for General Graphs 5
3 Algorithm for Cographs 15
4 Conclusion and Future Work 23
Bibliography 25

[1] L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed, P. Seymour, Bisimplicial vertices in even-hole-free graphs. Journal of Combinatorial Theory, Series B, pp.1119–1146, 2000.
[2] A. Berry, R. Pogorelcnik, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, Information Processing Letters, Vol.111, pp. 508–501, 2011.
[3] T. Biedl, Graph-theoretic algorithms, Lecture notes of a graduate course on university of Waterloo, 2005.
[4] J.R.S. Blair, B.W Peyton, An introduction to chordal graphs and clique trees, Engineering Physics and Mathematics Division, 1992.
[5] A. Brandstdt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999.
[6] A.E. Brouwer, W.H. Haemers, Spectra of graphs, Springer, 2011.
[7] F. Cazalsa, C. Karandeb, A note on the problem of reporting maximal cliques, Theoretical Computer Science, Vol. 407, pp. 564–568, 2008.
[8] D.G. Corneil, Lexicographic breadth first search A survey, Graph-Theoretic Concepts in Computer Science, pp. 1–19, 2005.
[9] M. De, S.C. Nandyb, S. Royc, In-place algorithms for computing a largest clique in geometric intersection graphs, Discrete Applied Mathematics 2014.
[10] D. Eppstein, The Traveling Salesman Problem for Cubic Graphs, Journal of Graph Algorithms and Applications, Vol. 11, pp. 61-81, 2007.
[11] M. Habib, V. Limouzy, On some simplicial elimination schemes for chordal graphs, Electronic otes in Discrete Mathematics, Vol. 32, pp. 125–132, 2009.
[12] M. Habiba, R. McConnell, C. Paul, L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, Vol. 234, pp. 59–84, 2000.
[13] M. Habib, C. Paul, A simple linear time algorithm for cograph recognition, Discrete Applied Mathematics, Vol 145, pp. 183–197, 2005
[14] C.T Hong, S. Hougardy, F. Maffray, N.V.R Mahadev, On simplicial and cosimplicial vertices in graphs, Discrete Applied Mathematics, Vol. 138, pp. 117-132, 2004.
[15] H.A Jung, On a Class of Posets and the corresponding comparability graphs, Journal OF Combinatorial Theory B, Vol. 24, pp. 125–133, 1978.
[16] H. Lerchs, On cliques and kernels structure of graphs, Department of Computer Science, 1972.
[17] D.J. Rose, Triangulated graphs and the elimination process, Journal of Mathematical Analysis And Application, Vol. 32, pp. 597–609, 1970.
[18] D.J. Rose, R. E.TarJan, Algoritimic aspects of vertex elimination, Proceedings of seventh annual ACM symposium on Theory of computing, pp. 245–254,1975.
[18] D.J. Rose, R. E.TarJan, Algoritimic aspects of vertex elimination, Proceedings of seventh annual ACM symposium on Theory of computing, pp. 245–254,1975.
[20] K. Vuskovic, Even-hole-free graphs: A Survey, Applicable Analysis and Discrete Mathematics, pp. 219–240, 2010.