We invite you to join us for our first lecture + pizza of Winter 2008. Emily Kirkman will be giving a talk entitled "Efficient Circular Planarity Testing" on Tuesday, Feb. 21st at 5:00 pm in PDL C-36. (Abstract below).
ABSTRACT: Efficient Circular Planarity Testing In studying inverse problems of electrical networks at the UW REU, it has been determined that the underlying electrical network is recoverable if the graph is circular planar. Given a graph with designated boundary, it is circular planar if it can be drawn in a disc with the boundary nodes on the disc boundary, and all interior nodes inside the disc with no edge crossings. We present an algorithmic approach to determining in linear time whether a graph with boundary is circular planar, which will be demonstrated with an implementation in Sage. We will start with basic definitions so it should be accessible to any undergraduate student. This is a great talk to attend if you are interested in working on Sage or participating in the summer UW REU.
Hilbert's 17th problem asked whether every non-negative polynomial over the reals can be written as a sum of squares of rational functions. This was proved in the affirmative by Artin in the 1930's initiating the field of real algebraic geometry which is concerned with finding real solutions to polynomial equations and inequalities. One of the cornerstones of this theory is the Positivstellensatz due to Stengle in 1974, which is the analog of Hilbert's Nullstellensatz over the reals. The most efficient current version of the positivstellensatz is due to Mihai Putinar who arrived at it via the theory of moments. This theorem has allowed all sorts of new techniques for polynomial optimization leading to many unexpected applications.
This talk is an exposition of the history of this fascinating subject initiated by Hilbert that weaves analysis and algebra together and has then lead into applications. Mihai is a fantastic speaker and the talk itself is a repeat of an AMS plenary address.