Home | Issues | About JGAA | Instructions for Authors |
Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019
DOI: 10.7155/jgaa.00524
Recognizing Stick Graphs with and without Length Constraints
Steven Chaplick,
Philipp Kindermann,
Andre Löffler,
Florian Thiele,
Alexander Wolff,
Alexander Zaft, and
Johannes Zink
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.
|
Journal Supporters
|