Segment endpoint visibility graphs are Hamiltonian

DOI10.1016/S0925-7721(02)00172-4MaRDI QIDQ1395575zbMATH OpenOpenAlexFDO

Authors 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

line segmentsHamiltonian graphvisibility graph

Mathematics Subject Classification ID

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

Recommendations

• The visibility graph of congruent discs is Hamiltonian
• Planar segment visibility graphs
• Hamiltonian-connected graphs
• Hamiltonian extendable graphs
• Hamilton paths in graphs whose vertices are graphs
• scientific article; zbMATH DE number 3987316
• scientific article; zbMATH DE number 2058271
• Hamiltonian paths and hamiltonian connectivity in graphs
• Connectivity and Hamiltonian connectedness of graphs

Cites work

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

Cited in

(15)

• Alternating paths through disjoint line segments
• Alternating paths along axis-parallel segments
• Reconstruction of Weakly Simple Polygons from Their Edges
• Two segment classes with Hamiltonian visibility graphs
• On the visibility graph of convex translates
• Vertex-colored encompassing graphs
• Circumscribing polygons and polygonizations for disjoint line segments
• The visibility graph of congruent discs is Hamiltonian
• Pointed binary encompassing trees: simple and optimal
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• Compatible geometric matchings
• Encompassing colored planar straight line graphs
• Compatible spanning trees
• Relative convex hulls in semi-dynamic arrangements
• scientific article; zbMATH DE number 7559209 (Why is no real title available?)

This page was built for publication: Segment endpoint visibility graphs are Hamiltonian

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