Clique-Width of Point Configurations

D 2020

Clique-Width of Point Configurations

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

Basic information

Original name

Clique-Width of Point Configurations

Authors

CAGIRICI, Onur (792 Turkey, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution), Filip POKRÝVKA (703 Slovakia, belonging to the institution) and Abhisekh SANKARAN (356 India)

Edition

Cham, Graph-Theoretic Concepts in Computer Science, WG 2020, p. 54-66, 13 pp. 2020

Publisher

Springer, Lecture Notes in Computer Science

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

References:

open access preprint URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/20:00114292

Organization unit

Faculty of Informatics

ISBN

978-3-030-60439-4

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-60440-0_5

Keywords in English

point configuration; order type; fixed-parameter tractability; relational structure; clique-width

Abstract

V originále

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.

Links

GA20-04567S, research and development project

Name: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Czech Science Foundation

MUNI/A/1050/2019, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX (Acronym: SV-FI MAV IX)

Investor: Masaryk University, Category A

MUNI/A/1076/2019, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20 (Acronym: SKOMU)

Investor: Masaryk University, Category A

Citovat

CAGIRICI, Onur, Petr HLINĚNÝ, Filip POKRÝVKA and Abhisekh SANKARAN. Clique-Width of Point Configurations. In Graph-Theoretic Concepts in Computer Science, WG 2020. Cham: Springer, Lecture Notes in Computer Science, 2020, p. 54-66. ISBN 978-3-030-60439-4. Available from: https://dx.doi.org/10.1007/978-3-030-60440-0_5.

@inproceedings{1676037,
   author = {Cagirici, Onur and Hliněný, Petr and Pokrývka, Filip and Sankaran, Abhisekh},
   address = {Cham},
   booktitle = {Graph-Theoretic Concepts in Computer Science, WG 2020},
   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},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-030-60439-4},
   pages = {54-66},
   publisher = {Springer, Lecture Notes in Computer Science},
   title = {Clique-Width of Point Configurations},
   url = {https://arxiv.org/abs/2004.02282},
   year = {2020}
}

TY  - JOUR
ID  - 1676037
AU  - Cagirici, Onur - Hliněný, Petr - Pokrývka, Filip - Sankaran, Abhisekh
PY  - 2020
TI  - Clique-Width of Point Configurations
PB  - Springer, Lecture Notes in Computer Science
CY  - Cham
SN  - 9783030604394
KW  - point configuration
KW  - order type
KW  - fixed-parameter tractability
KW  - relational structure
KW  - clique-width
UR  - https://arxiv.org/abs/2004.02282
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 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.
ER  -

CAGIRICI, Onur, Petr HLINĚNÝ, Filip POKRÝVKA and Abhisekh SANKARAN. Clique-Width of Point Configurations. In \textit{Graph-Theoretic Concepts in Computer Science, WG 2020}. Cham: Springer, Lecture Notes in Computer Science, 2020, p.~54-66. ISBN~978-3-030-60439-4. Available from: https://dx.doi.org/10.1007/978-3-030-60440-0\_{}5.

Detailed Information on Publication Record