Development of G-net (a software system for graph theory & algorithms) with special emphasis on graph rendering on raster output devices

Abstract

In this thesis we will describe the development of software functions that render graphical and textual information of G-Net(A software system for graph theory & algorithms) onto various raster output devices.Graphs are mathematical structures that are used to model very diverse systems such as networks, VLSI design, chemical compounds and many other systems where relations between objects play an important role. The study of graph theory problems requires many manipulative techniques. A software system (such as G-Net) that can automate these techniques will be a very good aid to graph theorists and professionals. The project G-Net, headed by Prof. Kunwarjit S. Bagga of the computer science department has the goal of developing a software system having three main functions. These are: learning basics of graph theory, drawing/manipulating graphs and executing graph algorithms.The thesis will begin with an introduction to graph theory followed by a brief description of the evolution of the G-Net system and its current status. To print on various printers, the G-Net system translates all the printable information into PostScript' files. A major part of this thesis concentrates on this translation. To begin with, the necessity of a standard format for the printable information is discussed. The choice of PostScript as a standard is then justified. Next,the design issues of translator and the translation algorithm are discussed in detail. The translation process for each category of printable information is explained. Issues of printing these PostScript files onto different printers are dealt with at the end.