Research on algorithms and theory of graph drawings

在矩形图形中，包括外表面在内的所有面都必须绘制为矩形。Thomassen给出了平面图有矩形图的充要条件。然而，该条件仅适用于最大度为Δ3的图。在本研究中，我们首先介绍了一种新的绘图方式，称为内矩形绘图，其中所有的内面必须是矩形，而外表面可以是一个平行于轴的多边形，如L形或T形多边形。然后，我们给出了一个平面图不仅对于Δ≦3而且对于一般Δ都有内矩形图的充要条件。我们还给出了一种寻找内矩形图的有效算法。这些结果解决了这三十年来的一个悬而未决的问题，并有许多实际应用。v我们提出了另一种新的画法，称为盒-矩形图，它是矩形图和盒正交图的推广。在此基础上，给出了一种寻找长方体图形的有效算法。该算法的时间与给定图中的顶点数成线性关系，因此时间复杂度是最优的，不能再提高了。用于设计VLSI布局的传统方法使用矩形图，并且可以产生其中一些模块将相邻的布局，尽管它们不应该相邻。对于直线图、凸图和影响矩形图等其他图形样式，我们得到了一种新的高效算法来寻找小面积的图形。特别地，我们成功地获得了求四连通平面图的直线图的算法。该算法需要的面积是已知算法所需面积的四分之一。

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.