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
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