论文标题
混合和定向间隔图
Coloring Mixed and Directional Interval Graphs
论文作者
论文摘要
混合图具有一组顶点，一组无向EGDES和一组有向弧。混合图$ g $的适当着色是一个函数$ c $，它分配给每个顶点$ g $一个正整数，以便对于$ g $中的每个边缘$ uv $，$ g $，$ c（u）\ ne c（v）$，对于每个arc $ uv $ uv $ g $ g $ g $，$ c $ c（$ c），$ c（u）<c（u）<c（v）$。对于混合图$ g $，色度数$χ（g）$是$ g $的任何适当着色的最小颜色。方向间隔图是一个混合图，其顶点对应于真实线上的间隔。这样的图在每两个间隔之间具有一个边缘，其中一个间隔包含在另一个间隔和每两个重叠间隔之间的弧线，该间隔针对右侧和末端的间隔。 此类图具有根据Sugiyama Framework的分层正交图绘图中的路由边缘的应用。颜色对应于路由边缘的轨道。我们展示了如何识别方向间隔图，以及如何有效地计算其色数。另一方面，对于混合间隔图，即可以通过边缘或任意任意方向的弧线连接两个相交间隔的图形，我们证明计算变色的数字是NP-HARD。
A mixed graph has a set of vertices, a set of undirected egdes, and a set of directed arcs. A proper coloring of a mixed graph $G$ is a function $c$ that assigns to each vertex in $G$ a positive integer such that, for each edge $uv$ in $G$, $c(u) \ne c(v)$ and, for each arc $uv$ in $G$, $c(u) < c(v)$. For a mixed graph $G$, the chromatic number $χ(G)$ is the smallest number of colors in any proper coloring of $G$. A directional interval graph is a mixed graph whose vertices correspond to intervals on the real line. Such a graph has an edge between every two intervals where one is contained in the other and an arc between every two overlapping intervals, directed towards the interval that starts and ends to the right. Coloring such graphs has applications in routing edges in layered orthogonal graph drawing according to the Sugiyama framework; the colors correspond to the tracks for routing the edges. We show how to recognize directional interval graphs, and how to compute their chromatic number efficiently. On the other hand, for mixed interval graphs, i.e., graphs where two intersecting intervals can be connected by an edge or by an arc in either direction arbitrarily, we prove that computing the chromatic number is NP-hard.
