论文标题
在转向正交表示
On Turn-Regular Orthogonal Representations
论文作者
论文摘要
一类有趣的正交表示，由所谓的转式规范组成，即那些不包含任何对彼此“指向彼此”的反射角的转角表示。对于这种表示h，可以在线性时间计算最小区域图，即，在H的所有可能分配的顶点和弯曲坐标的所有可能分配中，最小面积的图形。这种情况自然激发了哪些图表的研究接受了转向规则的正交表示。在本文中，我们确定了始终接受此类表示的双连接平面图的显着类别，可以在线性时间内计算。我们还描述了树木的线性时间测试算法，并提供了多项式时间算法，该算法测试了带有“小”面的双连接的平面图是否具有无弯曲的旋转正交表示。
An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other" inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such representations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a biconnected plane graph with "small" faces has a turn-regular orthogonal representation without bends.
