Segment endpoint visibility graphs are Hamiltonian

DOI10.1016/S0925-7721(02)00172-4zbMath1024.68111MaRDI QIDQ1395575

D. Massart

Publication date: 1 July 2003

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian graph; visibility graph; line segments

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

52A10: Convex sets in (2) dimensions (including convex curves)

05C45: Eulerian and Hamiltonian graphs

05C62: Graph representations (geometric and intersection representations, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Computing simple circuits from a set of line segments
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• A tight lower bound on the size of visibility graphs
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• On a counterexample to a conjecture of Mirzaian
• Two segment classes with Hamiltonian visibility graphs
• Can visibility graphs be represented compactly?
• Planar segment visibility graphs
• Topologically sweeping visibility complexes via pseudotriangulations
• Minimal tangent visibility graphs
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME
• Every set of disjoint line segments admits a binary tree