The DFS-heuristic for orthogonal graph drawing

摘要

In this paper, we present a new heuristic for orthogonal graph drawings, which creates drawings by performing a depth-first search and placing the nodes in the order they are encountered. This DFS-heuristic works for graphs with arbitrarily high degrees, and particularly well for graphs with maximum degree 3. It yields drawings with at most one bend per edge, and a total number of m - n + 1 bends for a graph with n nodes and m edges; this improves significantly on the best previous bound of m - 2 bends.