Research on algorithms and theory of graph drawings

点击翻译按钮获取中文摘要

In a rectangular drawing, all the faces including the outer face must be drawn as rectangles. Thomassen gave a necessary and sufficient condition for a plane graph to have a rectangular drawing. However, the condition applies only for a graph of maximum degree Δ three. In this research, we first introduce a new drawing style called an inner rectangular drawing, in which all inner faces must be rectangles but the outer face can be an axis-parallel polygon like an L-shape or T-shape polygon. We then give a necessary and sufficient condition for a plane graph to have an inner rectangular drawing not only for Δ≦3 but also for general Δ. We also give an efficient algorithm to find an inner rectangular drawing. These results solve an open problem for these thirty years, and have many practical applications.vWe propose another new drawing style called a box-rectangular drawing, which is a generalization of a rectangular drawing and a box-orthogonal drawing. We then obtain an efficient algorithm to find a box-rectangular drawing. The algorithm takes time linear in the number of vertices in a given graph, and hence the time complexity is optimal, and cannot be improved any more. A conventional method for designing a VLSI layout uses a rectangular drawing, and may produce a layout in which some modules would be adjacent although they should not be adjacent. A new method using our algorithm produces a layout without such an unwanted adjacency of modules.For other drawing styles such as a straight-line drawing, a convex drawing, and a rectangle-of-influence drawing, we obtain new efficient algorithms for finding drawings of small area. In particular, we succeeded in obtaining an algorithm to find a straight-line drawing of a four-connected plane graph. The algorithm requires one quarter of the area required by the known algorithm.