Analysis of Complex Networks

9.2 Molecular Graphs

Chemical diagrams that present molecules have been used in organic chemistry for centuries [54]. The orientation of atoms and the average length of bonds that attach them to each other vary and are influenced by factors such as the number of shared pairs of electrons, the characteristics of the atoms being joined, and the nature of their immediate environment. A molecular graph or chemical graph is an abstract representation of the structural formula of a chemical compound in terms of graph theory, which in this context refers to a collection of vertices (atoms) and a collection of edges that connect pairs of vertices (bonds). Vertices are labeled with the type of atom and bonds with bond types – single, double, or triple. The lengths of bonds and the angles between them are depicted in 2D diagrams and provide a simple representation of the molecule. Bonds have no direction and are described as unidirectional. The tree width is the maximum number of bonds attached to each atom and is restricted by the valency of atoms, which is 5 or less. This low number makes molecular graphs sparse. Bodlaender et al. checked the treewidth of 10,000 chemical structures in a biological database and found the maximum to be 4 [55]. Molecular graphs are typically planar, but nonplanar ones do exist [56].

The details depicted in molecular graphs need to be consistent with known characteristics of the atoms and bonds as a group, which include factors such as the following:

1. The ...