Abstract
Every 4-graph has an orthogonal drawing with vertices drawn as grid points, where a k-graph is a graph of maximum vertex degree k. However, any plane k-graph with k 5 does not have an orthogonal grid drawing. Note that in our drawing, edge crossings are allowed, but edgeoverlapping is not allowed. In order to draw graphs of arbitrarily high vertex degree, other objectslike rectangles have been used to represent the vertices of the graph. However, rectangular shapescould be fat or skinny, and hence irregular. This motivates us to investigate the representation ofvertices by consistent unit grid squares (instead of general rectangles).Our consideration is that with consistent shapes for all vertices, the drawn graphs have theadvantage of great clarity for visualization purposes. With such a kind of representation, 8-graphscan now be drawn, and thus we broaden the classes of graphs that we can draw to quite someextent.Our objective is to find a drawing with few bends per edge. We present quadratic-time algorithmsto construct the orthogonal grid drawing of 5-graphs and 6-graphs such that each edgecontains at most two bends, and to construct the orthogonal grid drawing of 8-graphs such thateach edge contains at most three bends. Moreover, we show that the decision problem of determiningwhether an 8-graph has an orthogonal grid drawing without edge-bends is NP-complete. Thelast result implies that the problem to minimize the number of bends on edges in the orthogonaldrawing under the model where vertices are represented as unit grid squares or even as generalrectangles is thus NP-complete.