Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope -1 and lie above this line. De Luca et al. [GD'18] considered the recognition problem of stick graphs for the case that the ordering of either one of the two sets  (STICK_A) is given and for the case that the ordering of both sets is given (STICK_AB). They showed how to solve both cases efficiently. In this paper, we improve the running times of their algorithms and consider new variants of STICK, where no ordering is given, STICK_A, and STICK_AB where the lengths of the sticks are given as input. We show that all new problem variants are NP-complete and give an efficient solution for STICK_AB with fixed stick lengths if there are no isolated vertices.
Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope -1 and lie above this line. De Luca et al. [GD'18] considered the recognition problem of stick graphs when no order is given (STICK), when the order of either one of the two sets is given (STICK_A) , and when the order of both sets is given (STICK_AB). They showed how to solve STICK_AB efficiently. In this paper, we improve the running time of their algorithm, and we solve STICK_A efficiently. Further, we consider variants of these problems where the lengths of the sticks are given as input. We show that these variants of STICK, STICK_A, and STICK_AB are all NP-complete . On the positive side, we give an efficient solution for STICK_AB with fixed stick lengths if there are no isolated vertices.
R
for the case that the ordering
when no order is given (STICK), when the order
A
is given
R
is given and for the case that the ordering
, and when the order
R
both cases
STICK_AB
R
times of their algorithms and consider new variants of STICK, where no ordering is given, STICK_A, and STICK_AB where
time of their algorithm, and we solve STICK_A efficiently. Further, we consider variants of these problems where
R
all new problem variants are
these variants of STICK, STICK_A, and STICK_AB are all
R
and
. On the positive side, we