2014/12/01 by Talon, Alexandre, Kratochvíl, Jan
#05C62 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1412.0540
We describe the missing class of the hierarchy of mixed unit interval graphs, generated by the intersection graphs of closed, open and one type of half-open intervals of the real line. This class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as quadratic-time algorithms that recognize graphs from this class and produce a corresponding interval representation if one exists. We also mention that the work in arXiv:1405.4247 directly extends to provide a quadratic-time algorithm to recognize the class of mixed unit interval graphs.