Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019
Recognizing Stick Graphs with and without Length Constraints
Vol. 24, no. 4, pp. 657-681, 2020. Regular paper.
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.
Submitted: November 2019.
Reviewed: January 2020.
Revised: February 2020.
Accepted: March 2020.
Final: March 2020.
Published: December 2020.
Communicated by Daniel Archambault and Csaba D. Tóth
article (PDF)