近年來，圖形繪製為一個經常受探討的議題。尤其是以正交畫法受到注目，其只用到垂直與水平線段來做圖形的畫法，因此容易讓人辨識圖形的樣貌。在平面及非平面的圖形上，都有研究其正交畫法。在此，我們只針對非平面圖做討論。正交畫法中所討論的議題有許多，像是減少每條邊上所需的彎曲數量，減少圖中總共所需的彎曲數，減少邊之間的交叉數量，等等。在過去的研究中，圖形中節點的形狀，往往會根據其維度的變化，而有所改變。此外，節點上每邊之間的距離，也會因為維度過高，而有所減少。因此，為了針對節點能有固定大小，而且每邊之間也有固定的距離。我們提供了一個演算法，將每個節點放在格網上，並且以對角線的方向來做擺放。同時，線段則是畫在格線上，用以清楚區別每條線段。使得圖形能夠兼顧，節點形狀以及每邊之間有清晰的呈現。在此方式下，我們的目標在於，求得每邊最多所需要用到的彎曲數量，以及整個圖形最多所需要使用到的面積。所得到的結論為，在圖形中節點維度不超過6以上，每邊能以最多2次彎曲畫出；節點維度不超過8以上，每邊能以最多3次彎曲畫出。面積則是限制在O(n2) 的大小。此外，針對圖形是否能夠，以每邊皆無彎曲的方式下畫出，我們證明其為一個NPC的問題。

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 edge
overlapping is not allowed. In order to draw graphs of arbitrarily high vertex degree, other objects
like rectangles have been used to represent the vertices of the graph. However, rectangular shapes
could be fat or skinny, and hence irregular. This motivates us to investigate the representation of
vertices by consistent unit grid squares (instead of general rectangles).

Our consideration is that with consistent shapes for all vertices, the drawn graphs have the
advantage of great clarity for visualization purposes. With such a kind of representation, 8-graphs
can now be drawn, and thus we broaden the classes of graphs that we can draw to quite some
extent.

Our objective is to find a drawing with few bends per edge. We present quadratic-time algorithms
to construct the orthogonal grid drawing of 5-graphs and 6-graphs such that each edge
contains at most two bends, and to construct the orthogonal grid drawing of 8-graphs such that
each edge contains at most three bends. Moreover, we show that the decision problem of determining
whether an 8-graph has an orthogonal grid drawing without edge-bends is NP-complete. The
last result implies that the problem to minimize the number of bends on edges in the orthogonal
drawing under the model where vertices are represented as unit grid squares or even as general
rectangles is thus NP-complete.

1 Introduction 1
1.1 Related Work . . . . . . . . . . . . . . . . . . . . . 2
1.2 Motivations .. . . . . . . . . . . . . . . . . . . . . 3
1.3 Outline . . .. . . . . . . . . . . . . . . . . . . . . 5

2 Preliminaries 6

3 Drawing 5-Graphs and 6-Graphs 9
3.1 Drawing 5-graphs . . .. . .. . . . . . . . . . . . . 14
3.2 Drawing 6-graphs . . . . . . . . . . . . . . . . . . 16

4 Drawing 8-Graphs 19

5 On Lower Bound of Bend Number per Edge 30
5.1 Lower Bound for 5-Graphs . . . . . . . . . . .. . . . 30
5.2 On Lower Bound for 8-Graphs . . . . . . . . . . . . 31
5.2.1 8-Graph with 9 Vertices . . . . . . . . . . . . . . 31
5.2.2 8-Graph with 10 Vertices . . . . . . . .. . . . . . 31
5.2.3 8-Graph with 11 Vertices . . . . . . . . . . . . . 47

6 Hardness Result 53

7 Conclusion and Future Work 64

[1] C. Batini, M. Talamo, and R. Tamassia. Computer aided layout of entity-relationship diagrams.
Journal of Systems and Software, 4, pp. 163-173, 1984.
[2] C. Batini, E. Nardelli, and R. Tamassia. A layout algorithm for data-flow diagrams. IEEE
Trans. on Software Engineering, SE-12(4), pp. 538-546, 1986.
[3] S. Bridgeman et al. An algorithm for interactive orthogonal graph drawing. In Proc. of GD
1997, pp. 303-308, 1997.
[4] U. Brandes and D. Wagner. Dynamic grid embedding with few bends and changes. In Proc.
Algorithms and Computation (ISAAC), pp. 89-98, 1998.
[5] T. C. Biedl, B. P. Madden, and I. G. Tollis. Drawing high-degree graphs with small grid-size.
Technical Report 37-96, RUTCOR, Rutgers University, November 1996.
[6] T. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. Computational Geometry:
Theory and Applications, 9, pp. 159-180, 1998.
[7] G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis. Algorithms for drawing graphs: an
annotated bibliography. Compupational Geometry: Theory and Applications, 4(5), pp. 235-282,
1994.
[8] M. Chrobat and T. H. Payne. A linear-time algorithm for drawing a planar graph on a grid.
Information Processing Letters, 54(4), pp. 241-246, 1995.
[9] D. Dolev, F. Leighton, and H. Trickey. Planar embeddings of planar graphs. Advances in
Compupting Research, 2, pp. 147-161, 1984.
[10] W. Didimo and G. Liotta. Computing orthogonal drawings in a variable embedding setting.
In K.-Y. Chwa and O. H. Ibarra, editors, Proc. Algorithms and Computation (ISAAC), volume
1553 of Lecture Notes in Comput. Sci., pp. 79-88, Springer, Berlin, 1998.
[11] H. De Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica,
1, pp. 41-51, 1990
[12] G. Di Battista, E. Pietrosanti, R. Tamassia and I. G. Tollis. Automatic layout of PERT
diagrams with XPERT. IEEE trans. on Visual Languages. 4, pp. 171-176, 1989.
[13] S. Even and G. Granot. Rectilinear planar drawings with few bends in each edge. Technical
Report 797, Computer Science Department, Technion, Israel Institute of Technology, 1994.
[14] M. Eiglsperger, S. P. Fekete, and G. W. Klau. Orthogonal graph drawing. In Proc. of GD
1999, pp. 121–171, 1999.
[15] U. Fossmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In Proc.
of GD 1995, pp. 254-266, 1995.
[16] U. Fossmeier and M. Kaufmann. Algorithms and area bounds for nonplanar orthogonal drawings.
In Proc. of GD 1997, pp. 134-145, 1997.
[17] M. Formann et al. Drawing graphs in the plane with high resolution. In Proceedings IEEE
Symposium on FOCS, pp. 86-95, 1990; SIAM Journal on Computing, 22(5), pp. 1035-1052,
1993.
[18] X. He. A simple linear time algorithm for proper box rectangular drawings of plane graphs.
Journal of Algorithms, 40(1), pp. 82-101, 2001.
[19] M. Lundy and A. Mees. Combinatorial algorithms for integrated circuit layout. Teubner/Wiley
and sons, Stuttgart/Chichester, 1990.
[20] M. Nollenburg and A. Wolff. A mixed-integer program for drawing high-quality metro maps.
In Proc. of GD 2005, 3843, pp. 321-333, 2006.
[21] A. Papakostas and I. G. Tollis. A pairing technique for area-efficient orthogonal drawings. In
Proc. of GD 1996, pp. 355-370, 1996.
[22] A. Papakostas and I. G. Tollis. Algorithms for area-efficient orthogonal drawings. Computational
Geometry: Theory and Applications, 9, pp. 83-110, 1998.
[23] A. Papakostas and I. G. Tollis. Orthogonal drawing of high degree graphs with small area and
few bends. In Proc. 5th Workshop on Algorithms and Data Structures, pp. 354-367, 1998.
[24] L. B. Protsko, P. G. Sorenson, J. P. Tremblay, and D. A. Schaefer. Towards the Automatic
Generation of Software Diagrams. IEEE Trans. on Software engineering, SE-17(1), pp. 10-21,
1991.
[25] D. Reiner et al. A database designer’s workbench in entity-relationship approach. In Proc. 5th
International Conference on the Entity-Relationship Approach, pp. 347-360, North-Holland,
1987.
[26] M. Schaffter. Drawing graphs on rectangular grids with at most 2 bends per edge. Discrete
Applied Math, 63, pp. 75-89, 1995.
[27] R. Tamassia. Planar orthogonal drawings of graphs. IEEE trans. on Circuits and Systems,
pp. 319-322, 1990.
[28] R. Tamassia et al. An experimental comparison of four graph drawing algorithms. Computational
Geometry: Theory and Applications, 7, pp. 303-325, 1997.
[29] R. Tamassia, I. G. Tollis, and J. Vitter. Lower bounds for planar orthogonal drawings of
graphs. Information Processing Letters, 39, pp. 35-40, 1991.
[30] L. Valiant. University considerations in VLSI circuits. IEEE Trans. on Comput., 30, pp. 135-
140, 1981.
[31] D. R. Wood. Minimising the number of bends and volume in 3-dimensional orthogonal graph
drawings with a diagonal vertex layout. Algorithmica, 39, pp. 235-253, 2004.