TABLE OF CONTENTS A graph consists of a set of vertices and a set of edges, each joining two vertices. 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, etc. as well as concrete things like maps, structures of machines, etc. A diagram of a computer network is depicted in Fig. 1.1, where each component of the network is drawn by a small circle and a connection between a pair of components is drawn by a straight line segment. We can consider this diagram as a drawing of a graph which represents information regarding interconnections of the computer network. The vertices of the graph represent components of the network and are drawn as small circles in the diagram, while the edges of the graph represent interconnection relationship among the components and are drawn by straight line segments. A graph may be used to represent any information, like interconnection information of a computer network, 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.
We now consider another example. The graph in Fig. 1.2(a) represents eight components and their interconnections in an electronic circuit, and...
