![]() | Only 14 pages are availabe for public view |
Abstract Networks, or graphs, arise in a natural way in many applications, together with the need to be drawn. Except for very small instances, drawing a network by hand becomes a very complex task, which must be performed by automatic tools. The field of graph drawing is concerned with finding algorithms to draw networks in an aesthetically pleasant way, based upon a certain number of aesthetic criteria that define what a good drawing, (synonyms: diagrams, pictures, layouts), of a graph should be. This problem can be found in many areas of computer sciences, such as in the computer networks, data networks, PERT network, class inter-relationship diagrams in object oriented databases and object oriented programs, VLSI circuits, visual programming interfaces, database design systems, software engineering, data mining and Web mining. Further applications can be found in other sciences and engineering disciplines, such as: medical science, chemistry, ci.vil eng!neering, cartography, graphics design and fine arts. For this problem we introduce new algorithms, which successfully obtain much better drawings for this problem than the previous algorithms. In This thesis, we have addressed the problem of constructing aesthetic drawing of planar graphs in the following directions: • Drawing planar graphs as triangulated straight-line drawing: In this direction, we present in this thesis a study of the previous algorithms for drawing planar graphs. Also, we introduced a new linear-time algorithm that finds an embedding of the graph as straight-line drawing in a rectangular grid with small area, which is the optimal result up to the date of writing this thesis as far as we know. • Drawing planar graphs with minimize area-requirement in grid drawing: In this direction, we investigate a new genetic algorithm. Our genetic algorithm was able to find layouts with no edge crossings in 90% of the test planar graphs. The optimum area-requirement was occurred of planar graphs where tested. • Drawing 3-connected graphs as convex drawing: In this direction, we present in this thesis a study of previous algorithms. Then. we introduced a new algorithm for drawing 3-connected graphs. Also we presented development of this algorithm to produce convex drawing in small area, which is the optimal result up to the date of writing this thesis as far as we know. • Drawing level graphs aesthetically in the grid: In this thesis, we investigate in this direction three algorithms for drawing a given level graph in the grid aesthetically. The area of the grid drawing has minimum width value. Also, the area of the drawing is under control in the width or the height of the grid, and we can draw any level graph in any specific fixed area. |