论文标题
平面串联平行图的计算弯曲最小正交图在线性时间
Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time
论文作者
论文摘要
平面4颗G的平面正交图（即，最多四个具有顶点学位的平面图）是无交叉图形的图形，将每个G的每个顶点映射到平面的每个顶点，并将$ G $的每个边缘映射到其端点之间的一系列水平和垂直段。 30年来，图形图中的一个长期开放的问题是，是否存在一种线性时间算法来计算最小弯曲数量的平面4图的正交图。术语“平面”表示输入图与平面嵌入在一起，该嵌入必须由图形保存（即，图形必须具有与输入图相同的面部）。在本文中，我们为广泛研究的一系列串联平行图做出了积极回答上述问题。我们的线性时间算法是基于平面串联平行图的表征，该图允许无弯曲的正交图。该表征是根据图形的每种三连电组件的正交螺旋性给出的。组件的正交螺旋性测量该组件在图的正交图中“滚动”了多少。
A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of $G$ to a sequence of horizontal and vertical segments between its end-points. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper, we positively answer the question above for the widely-studied class of series-parallel graphs. Our linear-time algorithm is based on a characterization of the planar series-parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph.
