Stick Graphs with Length Constraints
share
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.
READ FULL TEXT