%0 Journal Article %1 ckltwzz-sglc-JGAA20 %A Chaplick, Steven %A Kindermann, Philipp %A Löffler, Andre %A Thiele, Florian %A Wolff, Alexander %A Zaft, Alexander %A Zink, Johannes %D 2020 %J Journal of Graph Algorithms & Applications %K %N 4 %P 657--681 %R 10.7155/jgaa.00524 %T Stick Graphs with and without Length Constraints %V 24 %X Stick graphs are intersection graphs of horizontal and vertical line seg- ments 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.

@article{ckltwzz-sglc-JGAA20, abstract = {Stick graphs are intersection graphs of horizontal and vertical line seg- ments 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. \par 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.}, added-at = {2024-04-29T21:12:33.000+0200}, author = {Chaplick, Steven and Kindermann, Philipp and Löffler, Andre and Thiele, Florian and Wolff, Alexander and Zaft, Alexander and Zink, Johannes}, biburl = {https://www.bibsonomy.org/bibtex/2bccc546889a90ad9b427cd9a310c7fd8/awolff}, doi = {10.7155/jgaa.00524}, interhash = {878f18b1497e63a64afe89d6964d9b56}, intrahash = {bccc546889a90ad9b427cd9a310c7fd8}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {}, number = 4, pages = {657--681}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/ckltwzz-sglc-GD19-slides.pdf}, timestamp = {2024-04-29T21:12:33.000+0200}, title = {Stick Graphs with and without Length Constraints}, volume = 24, year = 2020 }