I would like to thank the many people who have helped me on the path towards this dissertation, both during and before my time at Stanford.
I am extremely grateful for the opportunity to have had Pat Hanrahan as an advisor for the past five years. Pat has been an inspiration to me since I first met him at The Geometry Center in 1991. When I was considering graduate schools a few years later, a major part of my decision-making procedure was to read through the previous decade of Siggraph proceedings. I ended up at Stanford because I found that the papers that most delighted me had Pat's name on them. What I value most about this past five years was the opportunity to absorb not only his insights into the specifics of my work, but his fundamental approach to research that emphasizes rigor and first principles.
I next thank the members of my reading committee for their time and energy in helping me improve this document: Marc Levoy, Terry Winograd, and Stephen North. I have had the pleasure of learning from them in other ways as well. Listening to a quarter of Marc's lectures on rendering as his teaching assistant provided a valuable lesson on how to simultaneously engage and challenge an audience. I was able to observe Terry's approach to project management through my involvement in the Interactive Mural project. Stephen's thorough knowledge of the field of graph drawing has been a valuable resource, and I appreciate his trip from the East Coast to attend my oral defense.
Several fellow graduate students share an interest in information visualization. My deepest gratitude is due to François Guimbretière for being a coauthor, a friend, and an intellectual sparring partner. His insightful commentary on drafts of this entire dissertation and many previous papers has been immensely useful in helping me clearly communicate my sometimes inchoate thoughts. Our innumerable hours spent discussing the issues of information visualization and related topics have been a major influence in my vision of the entire field. Maneesh Agrawala, Robert Bosch, Chris Stolte, and Diane Tang have been both intellectual and personal comrades, and have also spent many hours reading paper drafts.
I have enjoyed the company of my several officemates: thanks to Lucas Pereira for his stupendous enthusiasm and nearly irrepressible ability to take joy in life, Sean Anderson for many hours of illuminating conversations and the occasional piano serenade, Karen Butler for her level-headed companionship, and Larry Page for an uncounted number of jovial arguments.
I also thank many of the other people in the 3B wing who have contributed to its convivial atmosphere, including Andrew Beers, Cindy Chen, Greg Humphreys, Craig Kolb, David Koller, and Gordon Stoll. John Owens has gathered vast amounts of good karma by proofreading this entire document. Thanks to John Gerth for keeping the graphics lab machines running despite any and all fits of tempermentality on their part, and also for sharing his accumulated wisdom in the fields of visualization and graphics. Ada Glucksman's continual good cheer was contagious as she shielded me as much as possible from the bureaucratic maw of the university, as did Sarah Beizer. Thanks to James Davis for being my partner in adversity through the past four years of designing, building and supporting the video lab. Thanks also to Phil Lacroute, who helped me reverse-engineer and transport the previous video rack to the then-new Gates Building.
Thanks to many current and former people in the Stanford Computer Science department for their friendship over the years, including Guido Appenzeller, Edouard Bugnion, Stuart Cheshire, Tom Costello, Pavani Diwanji, Denis Leroy, Dave Ofelt, Anna Patterson, and Beth Seamans. Lise Getoor has in particular been my comrade in arms for the past five years.
I gratefully acknowledge the efforts of the rest of the Site Manager product team at Silicon Graphics: Ken Kershner, Greg Ferguson, Alan Braverman, Donna Scheele, Doug O'Morain, and Julie Brodeur. I also thank the following people and organizations for the use of the data used in Chapter 3: function call graph data from Anwar Ghuloum of the Stanford University Intermediate Format (SUIF) compilers group, Autonomous Systems data from Hans-Werner Braun of the National Laboratory for Applied Network Research (NLANR) and David M. Meyer of the University of Oregon Route Views Project, and Internet routing and Autonomous System data from Daniel W. McRobb of the Consortium for Applied Internet Data Analysis (CAIDA)
I am grateful for the time and ideas of the computational linguists from Microsoft Research who were the target users of the Constellation systems: Lucy Vanderwende, Bill Dolan, and Mo Corston-Oliver. Thanks also to Mike Barnett for providing MindNet support, Mary Czerwinski for her significant contributions to the user-centered design and evaluation process, and George Robertson of the User Interface group at Microsoft Research for hosting me as an intern during the summer of 1998.
This work was mainly supported by the National Science Foundation Graduate Research Fellowship Program and the Microsoft Research Graduate Fellowship Program. Additional support was also provided by the Advanced Research Projects Agency (grant 2DMA818) and Silicon Graphics. I am also grateful for the support of the SFB288 Differential Geometry and Quantum Physics group at the Technical University of Berlin, where I spent a refreshing and productive summer as a visiting researcher before starting the graduate program at Stanford.
I have had the great fortune of benefiting from the wisdom, encouragement, and friendship of many mentors. The somewhat roundabout causal chain that led me to this dissertation started with two junior high school teachers. In eighth grade my science teacher Dennis Searle encouraged me to apply for a formal industry mentorship program, which led me to spend the summer learning FORTRAN at Control Data's supercomputer division. I am extremely grateful that my mentor Dick Kachelmeyer gave his time unstintingly, both in person that summer and in many phone conversations over the years. He has been advising me to get a PhD since I was twelve years old, and my decision to both start grad school and stay here until finished is in no small part due to his unswerving advocacy. Dick was also instrumental in helping me find my first job in the computer industry: I spent three summers at Control Data's supercomputer spinoff company ETA Systems.
The other life thread started in sixth grade, when my math teacher Sally King allowed and encouraged me to start working independently. I ended up in the accelerated classes of the University of Minnesota Talented Youth Mathematics Project. This project not only gave me the opportunity to finish all the mathematics requirements for an engineering degree by the end of high school, but also led to my next summer job thanks to a follow-on program to help alumni find interesting internships. These two threads of my life intertwined when my resume was sent to the Geometry Supercomputer Project, in what appears to be a clear case of word-based pattern matching.
It was during my summer at the GSP that I fell in love with computer graphics, and I returned there as a technical staff member after I received my undergraduate degree from Stanford, by which time the GSP had become the NSF-funded Geometry Center. Charlie Gunn and Stuart Levy were both friends and mentors during my four years there, which were instrumental in shaping my career goals. I thank Charlie for sharing his experience through a broad range of lessons about graphics, mathematics, life in industry, and life in general. I am grateful that I was able to absorb a small part of Stuart's immense technical knowledge, and also to be exposed to his philosophy of life: he is the gentlest person that I have ever met, and one of the kindest. While at the Center, I also learned from Al Marden, Dick McGehee, Mark Phillips, and George Francis. I am also grateful for the continuing friendship of former colleagues Celeste Fowler and Nina Amenta.
I am thankful that many people in my field have offered both sound professional advice and welcome friendship, including Nancy Blachman, Paul Burchard, Andrew Hanson, Jan Hardenburgh, Mary Lou Jepsen, Bill Lorensen, Delle Maxwell, Theresa-Marie Rhyne, Maureen Stone, and Betsy Zeller. Many friends have helped me stay sane through these sometimes difficult years, including Ron Avitzur, Julian Cash, Karen Cassil, Thida Cornes, Cassidy Curtis, Craig DeForest, Collette Duplessis, John Gilmore, Ian Goldberg, Jed Hartman, Dikran Karagueuzian, Kevin Lahey, Sarah Liberman, Mark Lottor, Tsutomu Shimomura, Peter Shipley, Lynn Stewart, and Meg Worley.
Thanks to k claffy for being both a friend for the past dozen years and the impetus of the Planet Multicast project, introducing me to my coauthors Bill Fenner and Eric Hoffman. I am deeply appreciative of Eric's companionship, both intellectual and personal, over the past four years.
I acknowledge, appreciate, and return the love and support of my family, without whom I would be lost. My parents Joan and Aribert Munzner have been my emotional anchors through not only the vagaries of graduate school, but my entire life. My sister's partner Sheila Oehrlein has also become an important person in my world. My sister Naomi will always share a part of my soul, and I dedicate this thesis to her.