Recognizing Stick Graphs with and without Length Constraints - Chaplick, Steven; Kindermann, Philipp; Löffler, Andre; Thiele, Florian; Wolff, Alexander; Zaft, Alexander; Zink, Johannes (Journal of Graph Algorithms and Applications, 2020)
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 ($STICK$), when the order of either one of the two sets is given ($STICK_{\textsf 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_{\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 $STICK$, $STICK_{\textsf 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.