Characterizing and recognizing the visibility graph of a funnel-shaped polygon

DOI10.1007/BF01300372zbMath0837.68120MaRDI QIDQ1894711

Kyung-Yong Chwa, Seung-Hak Choi, Sung Yong Shin

Publication date: 27 August 1995

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

visibility algorithmsrecognition algorithmvisibility graphs\(F\)-graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (6)

A Characterization of Visibility Graphs for Pseudo-polygons ⋮ Reconstructing Generalized Staircase Polygons with Uniform Step Length ⋮ Computing the maximum clique in the visibility graph of a simple polygon ⋮ Visibility graphs of towers ⋮ Reconstructing Generalized Staircase Polygons with Uniform Step Length ⋮ A fast shortest path algorithm on terrain-like graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On recognizing and characterizing visibility graphs of simple polygons
• Weakly triangulated graphs
• Visibility and intersection problems in plane geometry
• Visibility of disjoint polygons
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• An optimal visibility graph algorithm for triangulated simple polygons
• Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains
• DISTANCE VISIBILITY GRAPHS
• Euclidean shortest paths in the presence of rectilinear barriers
• Recognizing visibility graphs of spiral polygons
• The NP-completeness column: an ongoing guide
• A linear-time algorithm for solving the strong hidden-line problem in a simple polygon
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• COMPLEXITY ASPECTS OF VISIBILITY GRAPHS

This page was built for publication: Characterizing and recognizing the visibility graph of a funnel-shaped polygon