2. Definitions and Notations

We use to denote an undirected graph, with the set of vertices and the set of edges. We assume the graph is connected. Disconnected graphs can be drawn by laying out each of the components separately.

If two vertices and form an edge, we denote that as . The coordinates of node are denoted as , and we use to denote the 2-norm distance between vertices and . We use to denote the graph distance between vertices and , and we use to denote the diameter of the graph.

The graph layout problem is one of finding a set of coordinates, , with or , for 2D or 3D layout, respectively, such that when the graph is drawn with vertices placed at these coordinates, the drawing is visually appealing.