Journal of Graph Algorithms and Applications Simultaneous Embedding of Planar Graphs with Few Bends
Journal of Graph Algorithms and Applications Simultaneous Embedding of Planar Graphs with Few Bends
复制标题
图算法与应用杂志 具有很少弯曲的平面图的同时嵌入
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
S. Kobourov
中科院分区：
文献类型：
--
作者：
C. Erten;S. Kobourov
我们考虑几个变化的同时嵌入问题的平面图。我们开始一个简单的证明，并不是所有的平面图对有同时的几何嵌入。然而，使用弯曲，平面图对可以同时嵌入O（n2）× O（n2）网格上，每条边最多有三个弯曲，其中n是顶点数。时间复杂度为O（n）的算法保证图中的两个对应顶点映射到最终绘图中的相同位置，并且两个绘图都没有交叉。当两个输入图都是树时的特殊情况有几个应用，例如等高线树简化和进化生物学。我们表明，如果两个输入图是树，只有一个弯曲每边是必需的。时间复杂度为O（n）的算法保证两个图都是无交叉的，对应的树顶点映射到相同的位置，所有顶点（和弯曲）都在O（n2）× O（n2）网格上（O（n3）× O（n3）网格）。对于其中一个图是树而另一个图是路径的特殊情况，我们可以找到具有固定边的同时嵌入。也就是说，我们可以保证对应的顶点映射到相同的位置，并且对应的边以相同的方式绘制。本文描述了一个O（n）时间的同时嵌入算法，该算法用于树路径对的固定边嵌入，树路径对的每个树边最多有一个弯曲，并且沿着路径边没有弯曲，使得所有顶点（和弯曲）都在O（n）× O（n2）网格上，（O（n2）× O（n3）网格）.
We consider several variations of the simultaneous embedding problem for planar graphs. We begin with a simple proof that not all pairs of planar graphs have simultaneous geometric embeddings. However, using bends, pairs of planar graphs can be simultaneously embedded on the O(n 2) × O(n 2) grid, with at most three bends per edge, where n is the number of vertices. The O(n) time algorithm guarantees that two corresponding vertices in the graphs are mapped to the same location in the final drawing and that both the drawings are without crossings. The special case when both input graphs are trees has several applications , such as contour tree simplification and evolutionary biology. We show that if both input graphs are trees, only one bend per edge is required. The O(n) time algorithm guarantees that both drawings are crossings-free, corresponding tree vertices are mapped to the same locations, and all vertices (and bends) are on the O(n 2) × O(n 2) grid (O(n 3) × O(n 3) grid). For the special case when one of the graphs is a tree and the other is a path we can find simultaneous embeddings with fixed-edges. That is, we can guarantee that corresponding vertices are mapped to the same locations and that corresponding edges are drawn the same way. We describe an O(n) time algorithm for simultaneous embeddings with fixed-edges for tree-path pairs with at most one bend per tree-edge and no bends along path edges, such that all vertices (and bends) are on the O(n) × O(n 2) grid, (O(n 2) × O(n 3) grid).