ABSTRACT
A drawing of a graph can be thought of as a diagram consisting of a collection of objects corresponding to the vertices of the graph together with some line segments corresponding to the edges connecting the objects. People are using diagrams from ancient time to represent abstract things like ideas, concepts, and so forth as well as concrete things like maps, structures of machines, and so on. A graph may be used to represent any information which can be modeled as objects and relationship between those objects. A drawing of a graph is a sort of visualization of information represented by the graph. The graph in Figure 23.1a represents eight components and their interconnections in an electronic circuit, and Figure 23.1b depicts a drawing of the graph. Although the graph in Figure 23.1a correctly represents the circuit, the representation is messy and hard to trace the circuit for understanding and troubleshooting. Furthermore, in this representation one cannot lay the circuit on a single layered PCB (printed circuit board) because of edge crossings. On the other hand, the drawing of the graph in Figure 23.1b looks better and it is easily traceable. Furthermore one can use the drawing to lay the circuit on a single layered PCB, since it has no edge crossing. Thus, the objective of graph drawing is to obtain a nice representation of a graph such that the structure of the graph is easily understandable, and moreover the drawing should satisfy some criteria that arises from the application point of view.
