# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Coloring Mixed and Directional Interval Graphs

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2208.14250.pdf

(Preprint), 777KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Gutowski, G., Mittelstädt, F., Rutter, I., Spoerhase, J., Wolff, A., & Zink, J. (2022). Coloring Mixed and Directional Interval Graphs. Retrieved from https://arxiv.org/abs/2208.14250.

Cite as: https://hdl.handle.net/21.11116/0000-000C-269B-B

##### Abstract

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 $\chi(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.

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 $\chi(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.