论文标题
扩展部分正交图纸
Extending Partial Orthogonal Drawings
论文作者
论文摘要
我们在部分表示扩展的框架内研究平面正交绘制样式。令$（g，h，γ_h）$为部分正交图，即G是一个图形，$ h \ subseteq g $是一个子图，而$γ_H$是H。我们表明的是$ g $ tests $ ge的$ g $ tests $γ_H的存在。如果存在这样的图纸，那么也有一个使用$ o（| v（h）|）$每个边缘弯曲。另一方面，我们表明找到一个延伸量可以最大程度地减少弯曲数量或每个边缘的弯曲数量固定数量是NP完整的。
We study the planar orthogonal drawing style within the framework of partial representation extension. Let $(G,H,Γ_H )$ be a partial orthogonal drawing, i.e., G is a graph, $H\subseteq G$ is a subgraph and $Γ_H$ is a planar orthogonal drawing of H. We show that the existence of an orthogonal drawing $Γ_G$ of $G$ that extends $Γ_H$ can be tested in linear time. If such a drawing exists, then there also is one that uses $O(|V(H)|)$ bends per edge. On the other hand, we show that it is NP-complete to find an extension that minimizes the number of bends or has a fixed number of bends per edge.
