Clique-width of point configurations

DOI10.1016/j.jctb.2021.09.001OpenAlexW4206974759MaRDI QIDQ5918571

Filip Pokrývka, Abhisekh Sankaran, Petr Hliněný, Onur Çağırıcı

Publication date: 23 November 2022

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.02282

zbMATH Keywords

relational structureorder typefixed-parameter tractabilityclique-widthpoint configuration

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx) Computing methodologies and applications (68Uxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On recognizing and characterizing visibility graphs of simple polygons
• Abstract order type extension and new results on the rectilinear crossing number
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• Enumerating order types for small point sets with applications
• Linear time solvable optimization problems on graphs of bounded clique-width
• Parameter analysis for guarding terrains
• Minimal representations of order types by geometric graphs
• Approximating clique-width and branch-width
• Recognizability, hypergraph operations, and logical types
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Point Visibility Graph Recognition is NP-Hard
• Multidimensional Sorting
• Terrain Guarding is NP-Hard
• Complexity of Some Geometric and Topological Problems
• Tree-Related Widths of Graphs and Hypergraphs
• Decomposing a Polygon into Simpler Components
• Computational complexity of art gallery problems
• Graph minors. II. Algorithmic aspects of tree-width
• Exact Algorithms for Terrain Guarding
• Finding Points in General Position
• Hitting and Piercing Rectangles Induced by a Point Set
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Area-Optimal Simple Polygonalizations: The CG Challenge 2019
• Recognizing Visibility Graphs of Triangulated Irregular Networks
• Orthogonal Terrain Guarding is NP-complete
• Limits of Order Types
• An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
• The Complexity of Order Type Isomorphism
• Finding Branch-Decompositions and Rank-Decompositions
• Computations by fly-automata beyond monadic second-order logic

This page was built for publication: Clique-width of point configurations