  Interval graphs, intersection graphs of segments on a real line (intervals),
play a key role in the study of algorithms and special structural properties.
Unit interval graphs, their proper subclass, where each interval has a unit
length, has also been extensively studied. We study mixed unit interval
graphs---a generalization of unit interval graphs where each interval has still
a unit length, but intervals of more than one type (open, closed, semi-closed)
are allowed. This small modification captures a much richer class of graphs. In
particular, mixed unit interval graphs are not claw-free, compared to unit
interval graphs.
  Heggernes, Meister, and Papadopoulos defined a representation of unit
interval graphs called the bubble model which turned out to be useful in
algorithm design. We extend this model to the class of mixed unit interval
graphs and demonstrate the advantages of this generalized model by providing a
subexponential-time algorithm for solving the MaxCut problem on mixed unit
interval graphs. In addition, we derive a polynomial-time algorithm for certain
subclasses of mixed unit interval graphs. We point out a substantial mistake in
the proof of the polynomiality of the MaxCut problem on unit interval graphs by
Boyaci, Ekim, and Shalom (2017). Hence, the time complexity of this problem on
unit interval graphs remains open. We further provide a better algorithmic
upper-bound on the clique-width of mixed unit interval graphs. Clique-width is
one of the most general structural graph parameters, where a large group of
natural problems is still solvable in the tractable time when an efficient
representation is given. Unfortunately, the exact computation of the
clique-width representation is \NP-hard. Therefore, good upper-bounds on
clique-width are highly appreciated, in particular, when such a bound is
algorithmic.
