Orthogonal Thickness of Graphs
Abstract
In this paper, we introduce the concept of orthogonal thickness of graph. Orthogonal thickness of a graph G is the minimum number of planar graphs with maximum degree less than or equal to 4 whose union is G. We compute lower and upper bounds for orthogonal thickness and show that they are tight.
Next, we introduce the concept of layered orthogonal drawing and develop an algorithm for layered orthogonal drawing of Kn in [n / 4] layers. Then, we extend the results to develop an algorithm for three-dimensional orthogonal (line-) drawing of Kn in a 2n * 2n * [n / 4] box. This drawing has at most 2 bends per edge and a total number of n(n-2) bends.
Keywords
Orthogonal Drawing, Three-Dimensional Orthogonal Drawing, Thickness, Geometric Thickness
