Graph Drawing Metrics and Representations with Applications

Much of graph drawing is based on drawing graphs as node-link diagrams, in which vertices are represented by points and edges are drawn as lines between the points. We first investigate a newly developed metric for measuring the quality of such a diagram called ply number, which is inspired by studying road networks. We then consider contact representations, in which vertices are represented by geometric shapes and edges exist as intersections along the boundaries of these shapes. Lastly, we conduct experiments in the use of graph drawing in visualizing the structure of computer programs.The ply number of a node-link drawing is defined as follows. For each vertex v, which is associated with a point in the plane, a disk is drawn centered on v with a radius of alpha times the length of the longest edge incident to v. The ply number is the maximum number of disks that overlap at a single point. We identify values of alpha for which a bounded-degree tree can be drawn with no two ply disks overlapping. We also show that for the customary value of alpha=1/2, all trees can be drawn with logarithmic ply number, with an area that is polynomial for bounded-degree trees. Lastly, we give a lower bound for the ply number of drawings of a specific class of 2-trees.We then study proper square-contact representations of planar graphs, in which any two squares are either disjoint or share infinitely many points along their boundary. We characterize the partial 2-trees and the triconnected cycle-trees allowing for such representations. We also study square-contact representations of general triconnected simply-nested graphs with respect to their outerplanarity index.Finally, we describe a graph visualization tool for visualizing Java bytecode. Our tool, which we call J-Viz, visualizes connected directed graphs according to a canonical node ordering, which we call the sibling-first recursive (SFR) numbering. We show through several case studies that the canonical drawing paradigm used in J-Viz is effective for identifying potential security vulnerabilities and repeated use of the same code in Java applications