Computing the obstacle number of a plane graph
From MaRDI portal
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Graph theory (including graph drawing) in computer science (68R10)
Abstract: An obstacle representation of a plane graph G is V(G) together with a set of opaque polygonal obstacles such that G is the visibility graph on V(G) determined by the obstacles. We investigate the problem of computing an obstacle representation of a plane graph (ORPG) with a minimum number of obstacles. We call this minimum size the obstacle number of G. First, we show that ORPG is NP-hard by reduction from planar vertex cover, resolving a question posed by [8]. Second, we give a reduction from ORPG to maximum degree 3 planar vertex cover. Since this reduction preserves solution values, it follows that ORPG is fixed parameter tractable (FPT) and admits a polynomial-time approximation scheme (PTAS).
This page was built for publication: Computing the obstacle number of a plane graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6226725)
