Clique-Width of Point Configurations

Investor logo

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CAGIRICI Onur HLINĚNÝ Petr POKRÝVKA Filip SANKARAN Abhisekh

Year of publication 2020
Type Article in Proceedings
Conference Graph-Theoretic Concepts in Computer Science, WG 2020
MU Faculty or unit

Faculty of Informatics

Citation
Web
Doi http://dx.doi.org/10.1007/978-3-030-60440-0_5
Keywords point configuration; order type; fixed-parameter tractability; relational structure; clique-width
Description 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 relate it to the 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info