A tight lower bound on the size of visibility graphs

DOI10.1016/0020-0190(87)90038-XMaRDI QIDQ1098639zbMATH OpenOpenAlexFDO

Authors Xiaojun 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

computational geometrylower boundcombinatorial geometryvisibility graph

Mathematics Subject Classification ID

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

Recommendations

• Minimal visibility graphs
• On the minimum size of visibility graphs
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• scientific article; zbMATH DE number 841640
• A fast algorithm for computing sparse visibility graphs

Cites work

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

Cited in

(16)

• On the minimum size of visibility graphs
• A fast algorithm for computing sparse visibility graphs
• VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME
• A note on minimal visibility graphs
• scientific article; zbMATH DE number 841640 (Why is no real title available?)
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• scientific article; zbMATH DE number 2077691 (Why is no real title available?)
• Lower bound for the size of maximal nontraceable graphs
• Can visibility graphs be represented compactly?
• Planar segment visibility graphs
• Minimal tangent visibility graphs
• Segment endpoint visibility graphs are Hamiltonian
• Minimal visibility graphs
• On sets of line segments featuring a cactus structure
• On the connectivity of visibility graphs
• Representations of graphs and networks (coding, layouts and embeddings)

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

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