This note presents a heuristic method for drawing graphs, which is effective for graphs with fewer than 30 vertices. The method is used in the TYGES system at the University of Queensland to layout graphs on limited two-dimensional surfaces. The key component of TYGES is the embedder, which assigns positions to vertices to create aesthetically pleasing layouts. The method aims to meet two criteria: equal edge lengths and maximum symmetry. These criteria contribute to an aesthetically pleasing layout in various applications.
The algorithm models the graph as a mechanical system with vertices as steel rings and edges as springs. The system is simulated by calculating forces on each vertex and moving them until the system reaches a minimal energy state. Two adjustments are made: logarithmic forces for springs and repulsion between nonadjacent vertices. The algorithm uses constants to control the forces and is efficient for graphs with fewer than 30 vertices.
Examples show the method's success with regular grid structures and sparse graphs, but it has limitations with dense graphs and graphs with few bridges. The algorithm is fast for trees and can be fine-tuned using a graph editor. It is acceptable for graphs with fewer than 50 vertices, but larger graphs are broken into smaller subgraphs.
The method shows promise for practical graph layout problems, though it has limitations for certain graph types. The authors acknowledge Leo Bradley's contributions and the support of the University of Virginia and McGill University's Computational Geometry Laboratory.This note presents a heuristic method for drawing graphs, which is effective for graphs with fewer than 30 vertices. The method is used in the TYGES system at the University of Queensland to layout graphs on limited two-dimensional surfaces. The key component of TYGES is the embedder, which assigns positions to vertices to create aesthetically pleasing layouts. The method aims to meet two criteria: equal edge lengths and maximum symmetry. These criteria contribute to an aesthetically pleasing layout in various applications.
The algorithm models the graph as a mechanical system with vertices as steel rings and edges as springs. The system is simulated by calculating forces on each vertex and moving them until the system reaches a minimal energy state. Two adjustments are made: logarithmic forces for springs and repulsion between nonadjacent vertices. The algorithm uses constants to control the forces and is efficient for graphs with fewer than 30 vertices.
Examples show the method's success with regular grid structures and sparse graphs, but it has limitations with dense graphs and graphs with few bridges. The algorithm is fast for trees and can be fine-tuned using a graph editor. It is acceptable for graphs with fewer than 50 vertices, but larger graphs are broken into smaller subgraphs.
The method shows promise for practical graph layout problems, though it has limitations for certain graph types. The authors acknowledge Leo Bradley's contributions and the support of the University of Virginia and McGill University's Computational Geometry Laboratory.