论文标题
平面三角形的定向直径
Oriented Diameter of Planar Triangulations
论文作者
论文摘要
无向图或有向图的直径定义为图中所有顶点的最大路径距离。给定一个无方向的图形$ g $，我们检查了将方向分配给$ g $的每个边缘的问题，以便最大程度地减少了所得图形的直径。所有紧密连接的方向上的最小直径称为$ g $的定向直径。确定图的定向直径的问题已知是NP - hard，但是时间复杂性问题对于平面图开放。在本文中，我们计算三角形网格图的定向直径的确切值。然后，我们证明了$ n/3 $下限和$ n/2+o（\ sqrt {n}）$上限在平面三角形的方向直径上。众所周知，鉴于平面图$ g $带有有界的树宽和固定的正整数$ k $，可以在线性时间确定$ g $的定向直径最多是$ k $。相比之下，我们考虑了定向直径问题的加权版本，并且表明它是具有有界路径的平面图的弱NP完整版。
The diameter of an undirected or a directed graph is defined to be the maximum shortest path distance over all pairs of vertices in the graph. Given an undirected graph $G$, we examine the problem of assigning directions to each edge of $G$ such that the diameter of the resulting oriented graph is minimized. The minimum diameter over all strongly connected orientations is called the oriented diameter of $G$. The problem of determining the oriented diameter of a graph is known to be NP-hard, but the time-complexity question is open for planar graphs. In this paper we compute the exact value of the oriented diameter for triangular grid graphs. We then prove an $n/3$ lower bound and an $n/2+O(\sqrt{n})$ upper bound on the oriented diameter of planar triangulations. It is known that given a planar graph $G$ with bounded treewidth and a fixed positive integer $k$, one can determine in linear time whether the oriented diameter of $G$ is at most $k$. In contrast, we consider a weighted version of the oriented diameter problem and show it to be is weakly NP-complete for planar graphs with bounded pathwidth.
