[talks] J Yoon general exam

Melissa M Lawson mml at CS.Princeton.EDU
Mon May 14 10:52:32 EDT 2007


 
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.



More information about the talks mailing list