| In the School of Electrical Engineering and Computer Science,a handful of researchers are using a rather uncommon tool to solve diverse and complex problems associated with computer science. The tool is graph theory, and it has played a large part in computer science. Without graph theory, for example, it would not have been possible to design modern computer chips, computer networks or even large computer programs. SEECS is proud of its well-known group of graph theory researchers led by Dr. Robert Brigham, Professor of Mathematics and Computer Science, Dr. Narsingh Deo, Millican Chair Professor of Computer Science and Dr. Ronald Dutton, Professor and CS Program Director. Each professor has an impressive body of graph theory research based on 20 to 30 years of work. Along with their current and past research assistants, Brigham, Deo and Dutton have created a unique niche as one of few university research programs to study computer-science based graph theory instead of math-based graph theory. |  |
| Solving Real World Problems "Computer science, essentially, solves real world problems," explained Dutton. "When you study real world problems, what you almost always have to do is take a description of that problem and map it into some object or picture that you can study." The resulting picture is a graph that almost any discipline can use to find a solution. In a graph, a problem or relationships are divided into discreet entities. Every entity is represented as a point on the graph (points are also called vertices or nodes). Each point is connected by a line (also called an edge) to form the graph. According to Deo, the origin of graph theory dates back to 1736 and Swiss mathematician Leonhard Euler. As a resident of Königsberg, Germany, Euler wondered if it was possible to cross the city's network of seven bridges only once during a walk across town. He mathematized his question and took the essential elements of the situation - the location of each bridge, for example - and represented them in a graph using lines and points. His graph proved that if there are more than two points (his graph had four points) with an odd number of lines to or from, it was not possible to cross all seven bridges just once. Euler published his findings in 1736 in what many consider to be the first documented use of graph theory. Despite this start more than 260 years ago, graph theory was not truly studied or utilized until recently. "There are descriptions of graph problems back in the middle ages," said Dutton. "So graph theory isn't really new but it's only been in the past 30 or 50 years that it became a real discipline in mathematics and other fields." So how does a mathematical model help solve computer science problems? Dutton explains that with a graph, researchers can state complex problems rather easily. Then they can study the properties (or problem) of the model independent of the application it came from. |
 |
| Complementary Disciplines "Computer science and graph theory complement each other," added Deo. "Computers allow us to solve very large problems concerning graphs, while on the other hand, graph theory helps advance computer science." One example Deo gave is that chip design - especially for very large microprocessors - wouldn't be possible without graph theory, yet that same microprocessor will power a computer to process a large graph. Graph theory was entirely new to Brigham and Dutton when they started studying it in the early 1980s. They learned on their own, and, over the past 20 years, the two professors have moved from a general study of graph theory into more specialized areas. "Initially, we were mainly trying to get that intuitive feel for how to work with graphs and how graphs relate to each other," recalled Dutton. "In the beginning, most of what we did stayed on the mathematical side of things. Over the years, we've moved to where we try to use graph theory to solve problems related to computer science." Brigham said, "Early on we did things with the structure of graphs and few graphs we worked on had to do with applications. But now, the number of ideas has expanded tremendously, and we find more applications for our solutions than ever before." Today, Brigham is working on a variety of projects, one being extremal graph theory and another is imbedding graphs into higher dimensional spaces. |  |
| Brad Pyle, a research assistant, has worked in several areas of graph theory alongside Brigham, including domination theory, colorings and competition graph theory. Pyle said, "So many different things can be modeled as a graph. And graph theory offers both a theoretical discipline and a practical discipline, which I like." He hopes to continue using graph theory and combinatorics in his future: "I'm in the process of applying to the National Security Agency. I've been assured that I'll use graph theory there, but they can't tell me how, of course!" |  |
| Abundant, Practical Applications Currently, Dutton is concentrating on alliance graphs with his research assistant, Khurram Hassan Shafique. Dutton said: "With alliance graphs, we look for groups of nodes that would have a strong bond between them, stronger between them than anything outside the group of nodes. This, quite possibly, has all kinds of uses … military applications, use by pharmaceutical companies and many others." Hassan Shafique became interested in graph theory after taking Deo's class in network optimization at UCF. He started with a broad study in the subject, and now is more in depth in his research. "I just presented a paper with Dr. Dutton entitled, "On Satisfactory Partition of Graphs," which has many practical applications, such as clustering problems and optimization problems of some types. I think that's what I like best, that there are so many applications of graph theory . It's now used in chemistry, social sciences, ecology, biology, geography and even psychology. It's amazing." Graph theory has been a major part of Deo's career, as well. His involvement in it goes back to the 1960s and his graduate student days at Northwestern University. Since, Deo has used graph theory to solve problems in computer science and electrical engineering, narrowing in on computational graph theory in particular. |  |
| A Unique Emphasis "Computational graph theory is applied to solve many problems in computer science," said Deo. "Our emphasis here, primarily, is on graph theory for computer science rather than the traditional mathematics-based graph theory. This focus is not found at many other universities." In fact, his book, "Graph Theory with Application to Engineering and Computer Science," was published by Prentice-Hall in 1974 and was the first of its kind, with emphasis on graph theory algorithms for computer science and engineering. This book is considered a classic and has been translated into many languages, including Russian, Polish and Portuguese. Now Deo is working on Web graphs: "The World Wide Web can be modeled as a directed graph where each node is a Web page and each hyperlink is an edge or line. Studying Web graphs gives insight into lots of things, such as Web algorithms for crawling, searching or ranking Web resources. Or if a virus spreads, we can use graph theory to see how it would travel through the Web. The Internet is a similar, large graph, and if you want to isolate certain cyber attacks, or something, you can do it using graph theory." Paulius Micikevicius, a research assistant with Deo, found graph theory appealing as he always liked puzzles and math. "That's the understatement of graph theory - it's like working on puzzles," said Micikevicius. "My graph theory classes with Deo and Brigham were very good - both are great teachers - and they fueled my interest." Now, he is working with Deo on tree graphs and on graph factorization, which is very applicable to computer science. He is also using graph theory to find the shape of a large molecule consisting of hundreds of thousands of atoms, which has many important applications in the design of pharmaceuticals. "At most universities, people mostly look at the math side of graph theory. What makes UCF and the School of EECS different is that Deo, Brigham, Dutton and the students really concentrate on computer science graph theory. It is a unique program of research," added Micikevicius. |  |
| Niche a Big Draw Zoran Nikoloski is also a research assistant with Deo. Graph theory interested Nikoloski in high school when he attended a special summer program in Yugoslavia. Later, he learned graph theory on his own and without a formal course. As an undergraduate studying computer science, he learned first-hand how well graph theory and computer science fit together. "When I was applying for Ph.D. programs, I realized Dutton, Brigham and Deo were all doing lots of work in graph theory at UCF. I knew they focused on the interrelation between graph theory and computer science and it was a big draw to this program." Now Nikoloski is working on tree labelings and a relatively new topic, random graph theory. He is working to implement random graph theory into specific problems, such as a Web graph, and finds this niche very interesting. "It is a subject that can branch off into lots of different directions. And that's what I like about graph theory - it is very creative and lots of problems from real life can be addressed with it. The application opportunities are huge." Brigham also believes there will continue to be tremendous use for graph theory in computer science and in a wide variety of disciplines. "I think there will continue to be more and more applications for graph theory outside of its math origins because graph theory solves practical problems." |  |
seecs network - issue 2 - spring 2002
For information or to submit story ideas contact Michelle Berberet, Information Specialist, at (407) 823-2750 or email: michelle@cs.ucf.edu
SEECS Network is a publication of the
Director's Office of the School of Electrical
Engineering and Computer Science at UCF:
PO Box 162362 * Orlando, FL 32816-2362
Phone: (407) 823-2341 * Fax: (407) 823-5419
©2002 www.seecs.ucf.edu