Two segment classes with Hamiltonian visibility graphs

DOI10.1016/0925-7721(94)90019-1MaRDI QIDQ1334612zbMATH OpenOpenAlexWikidataFDO

Authors Joseph O'Rourke, Jennifer Rippel

Publication date 25 September 1994

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(94)90019-1

zbMATH Keywords

Hamiltonian circuitvisibility graph

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

It has been conjectured that the visibility graph of a set of non- collinear disjoint line segments always contains a simple Hamiltonian circuit. The general problem and the problem for so-called shellable segments remain open, but the authors show that the conjecture holds for the class of independent segments (the line containing each segment misses all the other segments) and for the class of unit lattice segments (unit length segments whose endpoints have integer coordinates).

Recommendations

• Segment endpoint visibility graphs are Hamiltonian
• scientific article; zbMATH DE number 5239029
• Two New Classes of Hamiltonian Graphs
• scientific article; zbMATH DE number 4127257
• scientific article; zbMATH DE number 5846142
• scientific article; zbMATH DE number 1161243
• The visibility graph of congruent discs is Hamiltonian
• Two edge-disjoint Hamiltonian cycles in graphs
• Two theorems on Hamiltonian graphs
• scientific article; zbMATH DE number 908781

Cites work

• Computing simple circuits from a set of line segments
• Good splitters for counting points in triangles
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• scientific article; zbMATH DE number 49092 (Why is no real title available?)

Cited in

(10)

• On circumscribing polygons for line segments
• Segment endpoint visibility graphs are Hamiltonian
• A necessary condition for a graph to be the visibility graph of a simple polygon
• The visibility graph of congruent discs is Hamiltonian
• Circumscribing polygons and polygonizations for disjoint line segments
• scientific article; zbMATH DE number 866021 (Why is no real title available?)
• Circumscribing polygons and polygonizations for disjoint line segments
• Disproving a conjecture on planar visibility graphs
• On the visibility graph of convex translates
• Alternating paths along axis-parallel segments

This page was built for publication: Two segment classes with Hamiltonian visibility graphs

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