Time and error measures have limitations in revealing in-depth insights into effectiveness of graph visualizations. For better evaluations, this book introduces a cognitive approach. Three evaluations are presented with each using a different method measuring more than just time and error. These methods include purpose-designed questionnaires and interviews, cognitive load measures and eye tracking technology. Contributions of this work fall into two areas: evaluation methodology and domain knowledge. Our methodological contribution is that we define and apply a cognitive approach in evaluation of graph visualizations. A large set of empirical results and observations are produced demonstrating the usefulness of the cognitive approach. Contributions in improving our domain knowledge are diverse. These include (but not limit to) human sociogram perception conventions, a construct of cognitive load, a model of performance, mental effort and cognitive load, new measures of cognitiveload and visualization efficiency, a new concept of geodesic-path tendency. This work should be useful to practitioners, researchers and students in Visualization, User Interface and Human Factors fields.