 |
| Home | Issues | Aims and Scope | Instructions for Authors |
|
Just Accepted
This paper has been accepted to be published in the JGAA Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019. The paper will receive a volume, an issue number, and page numbers when the whole special issue will be published.
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. 0, no. 0, pp. 0-0, 0. 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.
Appeared on-line: March 2020.
|