A characterization of visibility graphs for pseudo-polygons

DOI10.1007/978-3-662-48350-3_51MaRDI QIDQ3452822zbMATH OpenOpenAlexFDO

Authors Qing Wang, Matt Gibson, Erik Krohn

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: In this paper, we give a characterization of the visibility graphs of pseudo-polygons. We first identify some key combinatorial properties of pseudo-polygons, and we then give a set of five necessary conditions based off our identified properties. We then prove that these necessary conditions are also sufficient via a reduction to a characterization of vertex-edge visibility graphs given by O'Rourke and Streinu.

Recommendations

• Negative results on characterizing visibility graphs
• scientific article; zbMATH DE number 4085050
• On recognizing and characterizing visibility graphs of simple polygons
• Visibility graphs and oriented matroids
• Non-stretchable pseudo-visibility graphs

Cites work

• A new necessary condition for the vertex visibility graphs of simple polygons
• Approximating theDomatic Number
• Characterizing and recognizing the visibility graph of a funnel-shaped polygon
• Decomposition of multiple coverings into more parts
• Epsilon nets and union complexity
• scientific article; zbMATH DE number 4085050 (Why is no real title available?)
• Negative results on characterizing visibility graphs
• Non-stretchable pseudo-visibility graphs
• On recognizing and characterizing visibility graphs of simple polygons
• Small-size -nets for axis-parallel rectangles and boxes
• The vertex-edge visibility graph of a polygon
• Unsolved problems in visibility graphs of points, segments, and polygons

Cited in

(12)

• Characterizing and recognizing the visibility graph of a funnel-shaped polygon
• Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains
• Negative results on characterizing visibility graphs
• Non-stretchable pseudo-visibility graphs
• Simple Characterization of LR-visibility Polygons
• A P-Completeness Result for Visibility Graphs of Simple Polygons
• Visibility Graphs of Anchor Polygons
• Visibility graphs of 2-spiral polygons (extended abstract)
• Recognizing Visibility Graphs of Triangulated Irregular Networks
• Characterizing LR-visibility polygons and related problems
• Coloring polygon visibility graphs and their generalizations
• On recognizing and characterizing visibility graphs of simple polygons

This page was built for publication: A characterization of visibility graphs for pseudo-polygons

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