| CAGIRICI, Onur, Petr HLINĚNÝ, Filip POKRÝVKA and Abhisekh SANKARAN. Clique-Width of Point Configurations. Journal of Combinatorial Theory, Ser B. Amsterdam: Elsevier B.V., 2023, vol. 158, No 1, p. 43-73. ISSN 0095-8956. Available from: https://dx.doi.org/10.1016/j.jctb.2021.09.001. |
Other formats:
BibTeX
LaTeX
RIS
@article{1799076,
author = {Cagirici, Onur and Hliněný, Petr and Pokrývka, Filip and Sankaran, Abhisekh},
article_location = {Amsterdam},
article_number = {1},
doi = {http://dx.doi.org/10.1016/j.jctb.2021.09.001},
keywords = {point configuration; order type; fixed-parameter tractability; relational structure; clique-width},
language = {eng},
issn = {0095-8956},
journal = {Journal of Combinatorial Theory, Ser B},
title = {Clique-Width of Point Configurations},
url = {http://dx.doi.org/10.1016/j.jctb.2021.09.001},
volume = {158},
year = {2023}
}
TY - JOUR
ID - 1799076
AU - Cagirici, Onur - Hliněný, Petr - Pokrývka, Filip - Sankaran, Abhisekh
PY - 2023
TI - Clique-Width of Point Configurations
JF - Journal of Combinatorial Theory, Ser B
VL - 158
IS - 1
SP - 43-73
EP - 43-73
PB - Elsevier B.V.
SN - 00958956
KW - point configuration
KW - order type
KW - fixed-parameter tractability
KW - relational structure
KW - clique-width
UR - http://dx.doi.org/10.1016/j.jctb.2021.09.001
N2 - While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and show that it is aligned with the general concept of clique-width of relational structures by Blumensath and Courcelle (2006). We also relate the new notion to monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given.
ER -
CAGIRICI, Onur, Petr HLINĚNÝ, Filip POKRÝVKA and Abhisekh SANKARAN. Clique-Width of Point Configurations. \textit{Journal of Combinatorial Theory, Ser B}. Amsterdam: Elsevier B.V., 2023, vol.~158, No~1, p.~43-73. ISSN~0095-8956. Available from: https://dx.doi.org/10.1016/j.jctb.2021.09.001.
|
