Janet Yoon will present her research seminar/general exam on Thursday May 17 at 10AM in Room 402. The members of her committee are Bob Tarjan (advisor), Andrea LaPaugh, and Bob Sedgewick. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ---------------------------------------------------- Planarity testing is used for many real-world applications such as circuit design. The first linear time planar embedding algorithm was introduced in 1974 by Hopcroft and Tarjan. More than thirty years later there continues to be an interest in this area. Efficiency is an important factor in the applicability of an algorithm, but just as crucial is its simplicity. I will first briefly introduce past algorithms; more specifically the algorithms of Cederbaum Even and Lempel, Boothe and Lueker, and Boyer and Mervold. Then I will introduce a better abstracted, simpler algorithm based on these algorithms. References [1] K. S. Booth and G. S. Lueker. Testing the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Com-put. Syst. Sci., 13:335-379, 1976. [2] J. M. Boyer and W. Myrvold. Stop minding your p's and q's: A simplified o(n) planar embedding algorithm. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, volume 13, pages 140-146, 1999. [3] Z. Galil, G. F. Italiano, and N. Sarnak. Fully dynamic planarity testing. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4, Victoria, B.C., Canada., pages 495-506, New York, 1992. ACM. [4] J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM 21,pages 549-558, Oct. 1976. [5] W-L Hsu. An efficient implementation of the pc-tree algorithm of shih and hsu's planarity test. Tech. Report, Inst of Inf Science,Academia Sinica, 1993. [6] J. Kleinberg and E. Tardos. Algorithm Design. Addison Wesley, 2005. [7] A. Lempel, A. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs: International Symposium, Rome, Italy., pages 215{232, New York, 1967. Gordon and Breach. [8] R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs.SIAM J. Appl. Math., 36:177-189, 1979. [9] R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. [10] Y. Makarychev. A short proof of kuratowski's graph planarity criterion. Journal of Graph Theory, 25:129-131, 1997. [11] J. M. Boyer P. F. Cortese M. Patrignani and G. Di Battista. Stop minding your p's and q's: Implementing a fast and simple dfs-based planarity testing and embedding algorithm. 2003. [12] W.-K. Shih and W.-L. Hsu. A new planarity test. Theoretical Computer Science, pages 179-191, 1999. [13] R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J.Comput., 1(2):146-160, 1972. [14] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, 1987. [15] R. M. McConnell W.-L. Hsu. Pq trees, pc trees, and planar graphs. Theoretical Computer Science, 296(1):59-74, 2003. [16] S. G. Williamson. Depth-first search and kurotowski subgraphs. Journal of the ACM, 31(4):681-693, 1984.