Computing the maximum clique in the visibility graph of a simple polygon

DOI10.1016/j.jda.2006.09.004zbMath1129.05048OpenAlexW1983271670MaRDI QIDQ2466015

Thomas C. Shermer, Subir Kumar Ghosh, Partha P. Goswami, Binay K. Bhattacharya

Publication date: 11 January 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.09.004

zbMATH Keywords

algorithmdynamic programmingconvexityHamiltonian cyclevisibility graphmaximum cliquesimple polygonconvex fanhidden vertex set

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

FO model checking on geometric graphs ⋮ Coloring polygon visibility graphs and their generalizations ⋮ On colourability of polygon visibility graphs ⋮ Unnamed Item ⋮ On Colourability of Polygon Visibility Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Visibility graphs of towers
• On recognizing and characterizing visibility graphs of simple polygons
• Characterizing and recognizing weak visibility polygons
• An optimal visibility graph algorithm for triangulated simple polygons
• Hiding people in polygons
• Visibility graphs and oriented matroids
• Characterizing and recognizing the visibility graph of a funnel-shaped polygon
• Non-stretchable pseudo-visibility graphs
• Recognizing visibility graphs of spiral polygons
• Computational complexity of art gallery problems
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS
• Inapproximability of finding maximum hidden sets on polygons and terrains

This page was built for publication: Computing the maximum clique in the visibility graph of a simple polygon