The Laboratory for Networks and Applied Graph Theory (GNAT) is an NSF funded laboratory that is engaged in fundamental and developmental research on distributed networks, graph systems and data visualization.

Distributed Networks. Research is being conducted on the design, implementation, and analysis of algorithms for the support of scalable and reliable communication services in distributed networks. A main goal of this research is to meet the important challenges that affect the national network-communication infrastructure and the needs of increasing numbers of network users and services. These challenges include mitigating the stress on network backbone caused by the diminishing locality of network traffic, easing the addition of large numbers of geographically distributed network hosts, implementing fault-tolerant and congestion-tolerant communication methods, and integrating diverse technologies such as fast-switching and mobile communication devices into the national networking infrastructure. A significant obstacle in meeting these challenges is the difficulty of routing, switching, addressing, and guaranteeing delivery of messages in such a large and growing global network. A NSF funded program of fundamental and applied research is being carried out attacking these scalability and reliability problems using techniques of network algorithms, computational combinatorics and graph theory.

Graph Systems. Fundamental and algorithmic research is being carried out on graph systems -- systems whose underlying topology or structure is a graph. Myriad important technologies have a graph as their underlying structure. Examples include networks (computer, communication, mobile, transportation, etc.) , connection machines for parallel computing, relational databases, VLSI layout, etc. In addition to basic research on graph systems software tools for simulating graph systems are being developed. The study of graph systems involves a combination of graph theory, computer science and systems engineering.

Data Visualization. Basic research is being done on the development of tools for data visualization including visualization of networks, graph systems and relational databases. The software package GUS (Graphs Underlying Systems) is being developed. This software package adds layers to standard graph drawing allowing the user to incorporate the additional features of the graph system.

Affiliations. Center for Mobile Computing, Laboratory for Integrated Network Computing (LINC),

Funding for Graduate Students. Funding is available for graduate students who have a strong background in computer science and mathematics. For more information see Fred Annexstein (Rhodes 889, e-mail: fred.annexstein@uc.edu) or Ken Berman (Rhodes 891, e-mail: ken.berman@uc.edu).

Web site: http://www.ececs.uc.edu/~berman/gnat/