We study the drawing of highly symmetric graphs, more precisely of cubic vertex transitive graphs. Classical force-directed algorithms, such as the Eades algorithm and the Fruchterman–Reingold algorithm, often produce satisfactory pictures, but the symmetries of the graph are usually not visible in them. We present an adaptation of the Fruchterman–Reingold algorithm in which, in addition to the graph, one of its automorphisms is given: the vertices are distributed on concentric circles corresponding to the cycles of the automorphism, and the algorithm then optimizes only the radii and rotations of the circles, so that the resulting drawing is always rotationally symmetric with respect to the given automorphism. We also describe a method which, for a given graph, tries to find an automorphism yielding the „nicest” drawing under this procedure. The algorithm is tested on graphs from the census of cubic vertex-transitive graphs, and we observe that the nicest drawings are typically obtained for automorphisms with few or zero fixed points and long cycles.
|
