首页> 外文期刊>Algorithmica >Ortho-polygon Visibility Representations of Embedded Graphs
【24h】

Ortho-polygon Visibility Representations of Embedded Graphs

机译:嵌入式图的多边形可视性表示

获取原文
获取原文并翻译 | 示例

摘要

An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be Omega(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs.
机译:n顶点嵌入图G(G的OPVR)的正多边形可见性表示形式是G的保留嵌入图形,该图将每个顶点映射到不同的正交多边形,并将每个边映射到其最终顶点之间的垂直或水平可见性。 G的OPVR的顶点复杂度是最小值k,因此每个多边形最多具有k个反射角。我们提出多项式时间算法,以测试G是否具有OPVR,如果有,则计算最小顶点复杂度之一。我们认为,G的OPVR的存在和顶点复杂性与它的每个边的交叉次数及其连通性有关。更确切地说,我们证明如果G的每个边缘最多具有一个交叉(即G是一个1平面图),则G的OPVR始终存在,而如果每个边缘允许两个交叉则可能不是这种情况。同样,如果G是3连通的1平面图,我们可以计算G的OPVR,其顶点复杂度受O(n)时间常数的限制。但是,如果G是2连通的1平面图,则G的任何OPVR的顶点复杂度可能为Omega(n)。相比之下,我们描述了2个连接的1平面图族,可以在O(n)时间内计算可保证恒定顶点复杂度的嵌入。最后,我们提出了关于1平面图的正交多边形可见性表示的顶点复杂度的实验研究结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号