Some results on point visibility graphs

DOI10.1016/j.tcs.2014.10.042zbMath1309.68195arXiv1209.2308OpenAlexW2962858036MaRDI QIDQ2339447

Subir Kumar Ghosh, Bodhayan Roy

Publication date: 1 April 2015

Published in: Theoretical Computer Science, Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

necessary conditionsplanar graphcomputational geometryPSPACEcharacterizing point visibility graphsrecognizing point visibility graphsvisibility embedding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Unit hypercube visibility numbers of trees ⋮ Reachable region query and its applications ⋮ On colouring point visibility graphs ⋮ Finding Points in General Position ⋮ Computational complexity aspects of point visibility graphs ⋮ Recognition and complexity of point visibility graphs ⋮ Some results on point visibility graphs

Cites Work

• Unnamed Item
• On the connectivity of visibility graphs
• The power of geometric duality
• Some results on point visibility graphs
• Drawings of planar graphs with few slopes and segments
• On the chromatic number of the visibility graph of a set of points in the plane
• A survey of Sylvester's problem and its generalizations
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Unsolved problems in visibility graphs of points, segments, and polygons
• Visibility Algorithms in the Plane

This page was built for publication: Some results on point visibility graphs