Computational complexity aspects of point visibility graphs

DOI10.1016/J.DAM.2018.06.016MaRDI QIDQ1720342zbMATH OpenOpenAlexFDO

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

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-hardnessgrid pointsspecial graph classesplanar embedding

Mathematics Subject Classification ID

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

Abstract: A point visibility graph is a graph induced by a set of points in the plane where the vertices of the graph represent the points in the point set and two vertices are adjacent if and only if no other point from the point set lies on the line segment between the two corresponding points. The set of all point visibility graphs form a graph class which is examined from a computational complexity perspective in this paper. We show NP-hardness for several classic graph problems on point visibility graphs such as Feedback Vertex Set, Longest Induced Path, Bisection and $mathcalF$-free Vertex Deletion (for certain sets $mathcalF$). Furthermore, we consider the complexity of the Dominating Set problem on point visibility graphs of points on a grid.

Recommendations

• Recognition and complexity of point visibility graphs
• Recognition and Complexity of Point Visibility Graphs
• Point visibility graph recognition is NP-hard

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Computational geometry. Algorithms and applications.
• Finding points in general position
• Fundamentals of parameterized complexity
• On the chromatic number of the visibility graph of a set of points in the plane
• On the complexity of \(k\)-SAT
• Recognition and complexity of point visibility graphs
• Some results in combinatorial geometry
• Some simplified NP-complete graph problems
• The node-deletion problem for hereditary properties is NP-complete
• Unit hypercube visibility numbers of trees
• Unsolved problems in visibility graphs of points, segments, and polygons
• Visibility Algorithms in the Plane
• Visibility graphs of point sets in the plane

Cited in

(5)

• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• Mutual visibility in graphs
• Recognition and complexity of point visibility graphs
• Point visibility graph recognition is NP-hard
• Recognition and Complexity of Point Visibility Graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1720342)