Research on algorithms and theory of graph drawings

在矩形图形中，所有面（包括外面）都必须绘制为矩形。Rassen给出了平面图有矩形图的一个充要条件。然而，该条件仅适用于最大度为Δ 3的图。在这项研究中，我们首先介绍了一种新的绘图风格称为内部矩形绘图，其中所有的内面必须是矩形，但外面可以是一个轴平行的多边形，如L形或T形多边形。然后，我们给出了平面图不仅对Δ φ 3而且对一般Δ都有内矩形图的一个充要条件.给出了一个求内矩形图的有效算法。这些结果解决了这三十年来的一个未解决的问题，并有许多实际应用。我们提出了另一种新的绘图样式，称为盒矩形绘图，它是矩形绘图和盒正交绘图的推广。然后，我们获得了一个查找矩形框绘图的有效算法。该算法的时间复杂度与给定图的顶点数成线性关系，因此时间复杂度是最优的，不能再提高。用于设计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.