...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Geodesic Obstacle Representation of Graphs
【24h】

Geodesic Obstacle Representation of Graphs

机译：图的测地线障碍表示

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-line segment connecting the points corresponding to two vertices does not intersect any obstacles if and only if the vertices are adjacent in the graph. The obstacle representation and its plane variant (in which the resulting representation is a plane straight-line embedding of the graph) have been extensively studied with the main objective of minimizing the number of obstacles. Recently, Biedl and Mehrabi [Therese C. Biedl and Saeed Mehrabi, 2017] studied non-blocking grid obstacle representations of graphs in which the vertices of the graph are mapped onto points in the plane while the straight-line segments representing the adjacency between the vertices is replaced by the L_1 (Manhattan) shortest paths in the plane that avoid obstacles.In this paper, we introduce the notion of geodesic obstacle representations of graphs with the main goal of providing a generalized model, which comes naturally when viewing line segments as shortest paths in the Euclidean plane. To this end, we extend the definition of obstacle representation by allowing some obstacles-avoiding shortest path between the corresponding points in the underlying metric space whenever the vertices are adjacent in the graph. We consider both general and plane variants of geodesic obstacle representations (in a similar sense to obstacle representations) under any polyhedral distance function in R^d as well as shortest path distances in graphs. Our results generalize and unify the notions of obstacle representations, plane obstacle representations and grid obstacle representations, leading to a number of questions on such representations.
机译：图形的障碍物表示是将顶点映射到平面中的点以及该平面的一组连接区域（称为障碍物）上，从而在以下情况下连接对应于两个顶点的点的直线段不会与任何障碍物相交：并且仅当顶点在图形中相邻时。障碍物表示及其平面变体（结果表示为图形的平面直线嵌入）已经得到了广泛的研究，其主要目的是最大程度地减少障碍物的数量。最近，Biedl和Mehrabi [Therese C. Biedl和Saeed Mehrabi，2017年]研究了图的无阻塞网格障碍表示，其中图的顶点映射到平面上的点上，而直线段则表示图之间的邻接顶点被平面上避开障碍物的L_1（曼哈顿）最短路径所取代。在本文中，我们介绍了图的测地线障碍物表示的概念，其主要目的是提供广义模型，当将线段视为欧几里得平面上的最短路径。为此，我们通过允许一些障碍来扩展障碍物表示的定义，即只要顶点在图形中相邻，避免在基础度量空间中相应点之间的最短路径。我们考虑了R ^ d中任何多面体距离函数以及图中最短路径距离下的测地障碍物表示形式的一般和平面变体（与障碍物表示相似）。我们的结果对障碍物表示，平面障碍物表示和网格障碍物表示的概念进行了概括和统一，从而引发了有关此类表示的许多问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号