A tight lower bound on the size of visibility graphs

DOI10.1016/0020-0190(87)90038-XzbMath0637.68076OpenAlexW1992635261MaRDI QIDQ1098639

Xiao-Jun Shen, Herbert Edelsbrunner

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90038-x

zbMATH Keywords

lower boundcombinatorial geometrycomputational geometryvisibility graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99) Compound decision problems in statistical decision theory (62C25)

Related Items (7)

Minimal visibility graphs ⋮ Minimal tangent visibility graphs ⋮ Segment endpoint visibility graphs are Hamiltonian ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ A note on minimal visibility graphs ⋮ VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME ⋮ On the minimum size of visibility graphs

Cites Work

• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Visibility of disjoint polygons

This page was built for publication: A tight lower bound on the size of visibility graphs