Segment endpoint visibility graphs are Hamiltonian

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

D. Massart

Publication date: 1 July 2003

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

Full work available at URL: https://doi.org/10.1016/s0925-7721(02)00172-4

zbMATH Keywords

Hamiltonian graphvisibility graphline segments

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (2) dimensions (including convex curves) (52A10) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Reconstruction of Weakly Simple Polygons from Their Edges ⋮ Alternating paths along axis-parallel segments ⋮ Circumscribing polygons and polygonizations for disjoint line segments ⋮ Compatible spanning trees ⋮ Compatible geometric matchings ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ Encompassing colored planar straight line graphs ⋮ Unnamed Item ⋮ Pointed binary encompassing trees: simple and optimal ⋮ Vertex-colored encompassing graphs ⋮ Alternating paths through disjoint line segments

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