Clique-Width of Point Configurations

被引：0

作者：

Cagirici, Onur ^{[1
]}

Hlineny, Petr ^{[1
]}

Pokryvka, Filip ^{[1
]}

Sankaran, Abhisekh ^{[2
]}

机构：

[1] Masaryk Univ, Fac Informat, Brno, Czech Republic

[2] Univ Cambridge, Dept Comp Sci & Technol, Cambridge, England

来源：

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2020 | 2020年 / 12301卷

关键词：

Point configuration; Order type; Fixed-parameter tractability; Relational structure; Clique-width; GRAPHS; SETS;

D O I：

10.1007/978-3-030-60440-0_5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：54 / 66

页数：13

共 27 条

[1]

Adler H, 2008, Arxiv, DOI arXiv:0806.0103

[2]

Aichholzer Oswin, 2017, International Journal of Computational Geometry & Applications, V27, P57, DOI 10.1142/S0218195917600044

[3] Enumerating order types for small point sets with applications [J].

Aichholzer, O ;

Aurenhammer, F ;

Krasser, H .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2002, 19 (03) :265-281

[4] Abstract order type extension and new results on the rectilinear crossing number [J].

Aichholzer, Oswin ;

Krasser, Hannes .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2007, 36 (01) :2-15

[5] Minimal Representations of Order Types by Geometric Graphs [J].

Aichholzer, Oswin ;

Balko, Martin ;

Hoffmann, Michael ;

Kyncl, Jan ;

Mulzer, Wolfgang ;

Parada, Irene ;

Pilz, Alexander ;

Scheucher, Manfred ;

Valtr, Pavel ;

Vogtenhuber, Birgit ;

Welzl, Emo .

GRAPH DRAWING AND NETWORK VISUALIZATION, 2019, 11904 :101-113

[6]

Aloupis Greg, 2014, P 25 ANN ACM SIAM S, P405, DOI DOI 10.1137/1.9781611973402.30

[7] Recognizability, hypergraph operations, and logical types [J].

Blumensath, A. ;

Courcelle, B. .

INFORMATION AND COMPUTATION, 2006, 204 (06) :853-919

[8]

Bonnet É, 2019, J COMPUT GEOM, V10, P21

[9] Linear time solvable optimization problems on graphs of bounded clique-width [J].

Courcelle, B ;

Makowsky, JA ;

Rotics, U .

THEORY OF COMPUTING SYSTEMS, 2000, 33 (02) :125-150

[10]

COURCELLE B, 1991, LECT NOTES COMPUT SC, V532, P253, DOI 10.1007/BFb0017394

← 1 2 3 →