Computational complexity aspects of point visibility graphs

DOI10.1016/j.dam.2018.06.016zbMath1404.05130arXiv1711.01811OpenAlexW2963984724MaRDI QIDQ1720342

Manuel Sorge, Anne-Sophie Himmel, Pascal Kunz, Vincent Froese, Clemens Hoffmann

Publication date: 8 February 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-hardnessplanar embeddinggrid pointsspecial graph classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Recognition and complexity of point visibility graphs
• The node-deletion problem for hereditary properties is NP-complete
• Some results in combinatorial geometry
• Some simplified NP-complete graph problems
• On colouring point visibility graphs
• Some results on point visibility graphs
• Unit hypercube visibility numbers of trees
• On the chromatic number of the visibility graph of a set of points in the plane
• Finding Points in General Position
• Unsolved problems in visibility graphs of points, segments, and polygons
• Visibility Algorithms in the Plane
• Visibility graphs of point sets in the plane
• On the complexity of \(k\)-SAT

This page was built for publication: Computational complexity aspects of point visibility graphs