Erdös Numbers for Computer Graphics Researchers

If you have an interest in mathematics, you have probably heard about the prolific mathematician Paul Erdös. It has become a pastime in the math community to find out how many links through co-authored papers it takes to get from a given mathematician to Erdös. Co-authors of Erdös have an Erdös Number of one, co-authors of his co-authors have an Erdös number of two, and so on.

Because computer graphics is founded on mathematics, it should come as no surprise that a number of computer graphics researchers have low Erdös numbers. If you are a graphics researcher, how can you find your own Erdös number? One way is to try the MathSciNet collaboration distance calculator. I have not actually not had much luck with this method for graphics researchers, however, most likely because the database does not containing many graphics publications. A better way is to start with the list of co-authors and co-co-authors of Erdös. It is a long list, but a few of the people on this list publish in the graphics community:

Agarwal, Pankaj Kumar
Bern, Marshall W.
Chazelle, Bernard M.
Dey, Tamal Krishna
Dobkin, David P.
Edelsbrunner, Herbert
Guibas, Leonidas J.
Hughes, John F.
Mitzenmacher, Michael
O'Rourke, Joseph
Snoeyink, Jack Scott
 Each of the above people have an Erdös Number of two, and they all have collaborated with a number of people in graphics. Note that many of them are computational geometers, which is a subject that forms a bridge between math and graphics. Using the DBLP Bibliography Server, I picked out some names in the graphics field from their co-author lists. The ACM Digital Library would be another good way to find such co-authors. The indented names below each have an Erdös Number of three. If you publish in graphics, you probably can find someone among them who is a short hop from you.

Agarwal, Pankaj Kumar
Brooks, Frederick P., Jr.
Cohen, Jonathan D.
Metaxas, Dimitris
Turk, Greg → Jessica Hodgins
Varshney, Amitabh
 Bern, Marshall W.
Amenta, Nina
Grimm, Cindy
 Chazelle, Bernard M.
Kazhdan, Michael → Hugues Hoppe
Rusinkiewicz, Szymon → Marc Levoy
Tal, Ayellet
 Dey, Tamal Krishna
Bajaj, Chandrajit
Zorin, Denis
 Dobkin, David P.
Finkelstein, Adam → Michael F. Cohen
Funkhouser, Thomas → Pat Hanrahan
Silver, Deborah
Sweldens, Wim
 Edelsbrunner, Herbert
Hamann, Bernd
Lin, Ming C.
Manocha, Dinesh
 Guibas, Leonidas J.
Adams, Bart
Gross, Markus → Heung-Yeung "Harry" Shum
Pai, Dinesh
Pauly, Mark
Pottmann, Helmut
Salesin, David → Donald Greenberg
Seidel, Hans-Peter
Veach, Eric
 Hughes, John F.
Aliaga, Daniel
Barr, Alan
Barzel, Ronen
Cani, Marie-Paule
Durand, Fredo
Igarashi, Takeo
Ju, Tao
Laidlaw, David
Markosian, Lee
Matusik, Wojciech
McGuire, Morgan
Nayar, Shree
Pfister, Hanspeter
Raskar, Ramesh
van Dam, Andries
Zeleznik, Robert
 Mitzenmacher, Michael
Marks, Joe
Owens, John
Sharf, Andrei
 O'Rourke, Joseph
Badler, Norman
 Snoeyink, Jack Scott
Alliez, Pierre
Isenberg, Martin
Lindstrom, Peter
van de Panne, Michiel
Pascucci, Valerio
Rossignac, Jarek
Shewchuk, Jonathan
 The above list has been augmented by links (→) to a few prolific graphics authors who have an Erdös Number of four.

Erdös-Bacon Numbers

In the entertainment industry, the equivalent of the Erdös Number is the Kevin Bacon Number. This is the number of links through feature films that it takes to reach the actor Kevin Bacon. An actor who was in a film with Kevin Bacon has a Bacon Number of one, and so on. There is, of course, a Bacon Number calculator, The Oracle of Bacon.

There is a small group of people who have both an Erdös Number and a Bacon Number, and the sum of these numbers is their Erdös-Bacon number. Believe it or not, there is a Wikipedia page on this topic.

Bernard Chazelle has a Bacon number of three (via the movie "Guy and Madeline on a Park Bench"), and an Erös number of two, giving him an Erdös-Bacon number of five. There are several researchers in graphics who have been extras on films, giving them Erdös-Bacon numbers. Randy Pausch had a part in the 2009 film Star Trek, in which the actor John Cho also appeared. John Cho was in the 2007 movie The Air I Breath with Kevin Bacon, which gives Randy Pausch a Bacon number of two. Since Randy's Erdös number is four, his Erdös-Bacon number is six. Dan Goldman was an extra on Star Wars II with Rose Byrne, giving him a Bacon number of two, and an Erdös-Bacon number of six. Eric Enderton was an extra on Star Wars I, which gives him a Bacon number of three, and an Erdös-Bacon number of seven.

Lower Bound

Finally, I will end with a discussion of possible lower bounds on Erdös-Bacon numbers. The following text is from Wikipedia's entry on the topic, which was deleted in 2009 due to overzealous editing:

Erdös himself may have an Erdös–Bacon number of 3, 4, or 6. Erdös' Erdös number is 0 by definition, and his Bacon number is currently 4 according to data from the Internet Movie Database. However, one of the links is disputed on the Erdös Number Project website. Without this link, his Bacon number rises to 6. Also, Sir Alec Guinness appears in N is a Number with Erdös. Although Guinness' name is not in the credits, this gives Erdös a Bacon-Erdös number of 3.

Daniel Kleitman, a mathematician at MIT, was an advisor for the movie Good Will Hunting and appeared briefly as an uncredited extra. Minnie Driver, who appeared in that movie, also appeared in Sleepers with Kevin Bacon; as such, Kleitman's Bacon number is 2. He also coauthored a paper with Erdös. This gives him an Erdös–Bacon number of 3.

The only ways a lower Erdös-Bacon number could be achieved would be: