Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00608
Finding a Maximum Clique in a Grounded 1-Bend String Graph
Vol. 26, no. 4, pp. 553-575, 2022. Regular paper.
Abstract A grounded 1-bend string graph is an intersection graph of a set of polygonal lines, each with one bend, such that the lines lie above a common horizontal line $\ell$ and have exactly one end point on $\ell$. We show that the problem of finding a maximum clique in a grounded 1-bend string graph is APX-hard, even for strictly $y$-monotone strings. For general 1-bend strings, the problem remains APX-hard even if we restrict the position of the bends and end points to lie on at most three parallel horizontal lines. We give fast algorithms to compute a maximum clique for different subclasses of grounded segment graphs, which are formed by restricting the strings to various forms of $L$-shapes.
 This work is licensed under the terms of the CC-BY license.
Submitted: June 2021.
Reviewed: March 2022.
Revised: May 2022.
Reviewed: October 2022.
Revised: November 2022.
Accepted: November 2022.
Final: December 2022.
Published: December 2022.
Communicated by Ignaz Rutter
article (PDF)
BibTeX