Coloring mixed and directional interval graphs

DOI10.1007/978-3-031-22203-0_30MaRDI QIDQ6172218zbMATH OpenOpenAlexFDO

Authors Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter, Joachim Spoerhase, Alexander Wolff, Johannes Zink

Publication date 16 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.14250

zbMATH Keywords

directed interval graphsmixed graphsmixed interval graphsproper coloringrecognition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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)ec(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.

Cites work

• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A note on mixed tree coloring
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Coloring mixed and directional interval graphs
• Completing orientations of partially oriented graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3545685 (Why is no real title available?)
• Layered drawing of undirected graphs with generalized port constraints
• Mixed graph colorings
• Modular decomposition and transitive orientation
• On the upward planarity of mixed plane graphs
• On two coloring problems in mixed graphs
• Upward and quasi-upward planarity testing of embedded mixed graphs

Cited in

(3)

• Mixed graph edge coloring
• Coloring mixed and directional interval graphs
• Coloring and recognizing mixed interval graphs

This page was built for publication: Coloring mixed and directional interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172218)