21much of theearlywork inthe20thcenturyontheFour ColorProblemwasfocusedon showing that certain configurations were reducible. Often showing that even oneconfigurationwasreduciblebecame amonumentaltask.Inthe1960sHeeschhadstreamlined Birkhoff's approach of establishing the reducibility of certain configu-rations.One of these techniques, called D-reduction, was sufficiently algorithmicin nature to allow this technique to be executed on a computer and, in fact, acomputer program for implementingD-reducibility was written on the CDC1604Acomputer by Karl Dirre, a graduate of Hanover.Because of the large number of ways that the vertices on the ring of a configu-ration could be colored,theamount of computer time needed to analyze complexconfigurations became a major barrierto their work. Heesch was then ableto de-velop a new method, called C-reducibility, where only some of the colorings of thering vertices needed to be considered. Of course, one possible way to deal with theobstacles that Heesch and Dirrewerefacing was tofind a morepowerful computeron which to run Dirre'sprogram.While Haken had attended Heesch's talk at the University of Kiel on the FourColorProblem,thelecturesthat seemed tointerestHakenthemost werethoseontopology given by Karl Heinrich Weise in which he described three long-standingunsolved problems.One of these was thePoincare Conjectureposed bythegreatmathematician and physicist Henri Poincare in 1904 and which concerned the rela-tionship of shapes, spaces,and surfaces.Another wastheFour ColorProblem andthe third was a problem in knot theory. Haken decided to attempt to solve all threeproblems. Although his attempts to prove thePoincare Conjecture failed, he wassuccessful with the knot theory problem.A proof of the Poincare Conjecture by theRussian mathematician Grigori Perelman was confirmed and reported in Trieste,Italyon17June2006.For this accomplishment,he wasawarded aFields Medal(themathematical equivalent of the Nobel Prize) on 22August 2006.However,Perelman declined to attend the ceremony and did not accept the prize. As for theFour Color Problem, the story continues.Haken's solution of the problem in knot theory led to his being invited to theUniversity of Illinois as a visiting professor. After leaving the University of Illinoisto spend some time at the Institute for Advanced Study in Princeton, Haken thenreturned to the University of Illinois to take a permanent position.Heesch inquired, through Haken, about the possibility of using the new super-computer at the University of Illinois (the ILLAC IV) but much time was stillneeded to complete its construction. The Head of the Department of ComputerScience there suggested that Heesch contact Yoshio Shimamoto, Head of the Ap-plied Mathematics Department at the Brookhaven Laboratory at the the UnitedStates Atomic Energy Commission, which had access to the Stephen Cray-designedControl Data 6600, which was thefastest computerat that time.Shimamoto himself had an interest in theFour ColorProblem and had eventhought of writing his own computer program to investigate the reducibility of con-figurations.ShimamotoarrangedforHeeschand DirretovisitBrookhaveninthelate1960s.Diuirrewasableto testmanconfigurationsforreducibility.Theconfigurations that were now known to be D-reducible still did not constitute an21 much of the early work in the 20th century on the Four Color Problem was focused on showing that certain configurations were reducible. Often showing that even one configuration was reducible became a monumental task. In the 1960s Heesch had streamlined Birkhoff’s approach of establishing the reducibility of certain configu￾rations. One of these techniques, called D-reduction, was sufficiently algorithmic in nature to allow this technique to be executed on a computer and, in fact, a computer program for implementing D-reducibility was written on the CDC 1604A computer by Karl D¨urre, a graduate of Hanover. Because of the large number of ways that the vertices on the ring of a configu￾ration could be colored, the amount of computer time needed to analyze complex configurations became a major barrier to their work. Heesch was then able to de￾velop a new method, called C-reducibility, where only some of the colorings of the ring vertices needed to be considered. Of course, one possible way to deal with the obstacles that Heesch and D¨urre were facing was to find a more powerful computer on which to run D¨urre’s program. While Haken had attended Heesch’s talk at the University of Kiel on the Four Color Problem, the lectures that seemed to interest Haken the most were those on topology given by Karl Heinrich Weise in which he described three long-standing unsolved problems. One of these was the Poincar´e Conjecture posed by the great mathematician and physicist Henri Poincar´e in 1904 and which concerned the rela￾tionship of shapes, spaces, and surfaces. Another was the Four Color Problem and the third was a problem in knot theory. Haken decided to attempt to solve all three problems. Although his attempts to prove the Poincar´e Conjecture failed, he was successful with the knot theory problem. A proof of the Poincar´e Conjecture by the Russian mathematician Grigori Perelman was confirmed and reported in Trieste, Italy on 17 June 2006. For this accomplishment, he was awarded a Fields Medal (the mathematical equivalent of the Nobel Prize) on 22 August 2006. However, Perelman declined to attend the ceremony and did not accept the prize. As for the Four Color Problem, the story continues. Haken’s solution of the problem in knot theory led to his being invited to the University of Illinois as a visiting professor. After leaving the University of Illinois to spend some time at the Institute for Advanced Study in Princeton, Haken then returned to the University of Illinois to take a permanent position. Heesch inquired, through Haken, about the possibility of using the new super￾computer at the University of Illinois (the ILLAC IV) but much time was still needed to complete its construction. The Head of the Department of Computer Science there suggested that Heesch contact Yoshio Shimamoto, Head of the Ap￾plied Mathematics Department at the Brookhaven Laboratory at the the United States Atomic Energy Commission, which had access to the Stephen Cray-designed Control Data 6600, which was the fastest computer at that time. Shimamoto himself had an interest in the Four Color Problem and had even thought of writing his own computer program to investigate the reducibility of con- figurations. Shimamoto arranged for Heesch and D¨urre to visit Brookhaven in the late 1960s. D¨urre was able to test many more configurations for reducibility. The configurations that were now known to be D-reducible still did not constitute an