Recognizing Stick Graphs with and without Length Constraints

Abstract

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. [De Luca et al. GD'18] considered the recognition problem of stick graphs when no order is given ($\textsf{STICK}$), when the order of either one of the two sets is given ($\textsf{STICK}_{\textsf A}$), and when the order of both sets is given ($\textsf{STICK}_{\textsf{AB}}$). They showed how to solve $\textsf{STICK}_{\textsf{AB}}$ efficiently. In this paper, we improve the running time of their algorithm, and we solve $\textsf{STICK}_{\textsf 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 $\textsf{STICK}$, $\textsf{STICK}_{\textsf A}$, and $\textsf{STICK}_{\textsf{AB}}$ are all NP-complete. On the positive side, we give an efficient solution for $\textsf{STICK}_{\textsf{AB}}$ with fixed stick lengths if there are no isolated vertices.