Special subgraphs of weighted visibility graphs

DOI10.1016/0020-0190(92)90014-MMaRDI QIDQ1199937zbMATH OpenFDO

Authors F. R. Hsu, R. C. T. Lee, R. C. Chang

Publication date 17 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90014-M

zbMATH Keywords

Euclidean distancepolygonweighted visibility graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

We are interested in finding a subgraph of a weighted visibility graph \(G\) with a small number of edges such that any arbitrary shortet path on \(G\) is almost entirely covered by the subgraph.

Recommendations

• Some results on visibility graphs
• A note on visibility graphs
• A general notion of visibility graphs
• On the connectivity of visibility graphs
• scientific article; zbMATH DE number 841640
• On k-visibility graphs
• Vertex-weighted graphs and their applications
• Visibility graphs and oriented matroids
• Constrained visibility representations of graphs
• Variety of mutual-visibility problems in graphs

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Maintenance of configurations in the plane
• Optimal shortest path queries in a simple polygon
• Triangulating a simple polygon in linear time
• Visibility and intersection problems in plane geometry

This page was built for publication: Special subgraphs of weighted visibility graphs

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