Efficient orthogonal drawings of high degree graphs (Q1969947)

Orthogonal drawings of graphs of high degree (more than four) are concerned. At first, the authors present a short survey of earlier papers concerning orthogonal drawings of graphs. It is mentioned that the algorithm proposed by Biedl possess better estimates of the drawing area for rather dense graphs than the given in this paper algorithm \ does. Then, the authors investigate the Simple Algorithm for explaining the basic visualization techniques followed. Next, the algorithm BOX\_ORTHOGONAL for orthogonal drawings of simple graphs with degree higher than four is developed. The algorithm contains several phases. The first phase called the preprocessing phase concerns enumeration of vertices that they follow to enter the drawing. Then, the vertices are paired and grouped consisting two and more than two vertices, respectively. Next, the authors develop the placement technique of the vertices in order to diminish the number of necessary bends, several cases are discussed. The algorithm characterize: * total number of bends at most \(m-2,\) * at most one bend per edge, * the area of produced drawing is at most \((m-1)\times (m/2+2),\) * running time is \(O(m),\) where \(m\) is the number of edges. The placement techniques applied reduce the number of crossings needed, nevertheless the number of crossings is not estimated. That makes the estimates for the number of bends actually less significant. The Ph. thesis of Papakostas is recalled for detailed applications concerning also 3D drawings.