A Study Of Some Efficient Algorithms For Drawing Graphs

Abstract

The problem of autom tic graph drawing has attracted recently a lot of attention, due to its numerous practical applications in mathematics, computer science and other branches. 'ln many applications graphical representations · are used for displaying information. The function of these representations is to clarify or to display the structure of the information in a compact and relatively small space. Many times one picture says more than thousand words, but the picture has to be clear and readable. Almost every body is aware of schemas, using rectangles with information, and lines and arrows connecting them. If a schema is small, then it can easily be drawn by hand. The problem becomes more and more difficult if one tries to draw the electrical diagrams of electrical applications in a readable form. The electrical schema of e.g. a television set gives a readable idea how the different components in the television are connected with each other. On the other hand, a computer is also used to calculate the optimal placement of the components inside the electrical application. The application contains a numerous amount of small electrical components, which must be connected with each other. These components have to be placed on a chip, such that the number of crossings between the connections is as small as possible, and the required area of the chip must not become too large. To compute an optimal placement of the components on a chip by hand requires an incredible amount of time. The problem becomes even more complex when several additional constraints have to be satisfied as well, e.g., the number of bends and the total length of the connections must be minimized as well. These questions arise in the design ofVery Large Scale Integration (VLSI) chips. This thesis presents efficient algorithms for drawing planar graphs. Graph drawing addresses the problem of constructing geometric representation of information and finds applications in almost every branch of science and technology. In this thesis we study triangulated