On the visibility graph of convex translates

DOI10.1016/S0166-218X(00)00270-5MaRDI QIDQ5951963zbMATH OpenFDO

Authors Kiyoshi Hosono, Henk Meijer, David Rappaport

Publication date 28 October 2002

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

matchingHamiltonian pathvisibility graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The visibility graph of congruent discs is Hamiltonian
• Segment endpoint visibility graphs are Hamiltonian
• scientific article; zbMATH DE number 4085050
• Two segment classes with Hamiltonian visibility graphs
• Minimal visibility graphs

Cites work

• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• scientific article; zbMATH DE number 1049272 (Why is no real title available?)
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Computational Geometry in C
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Convex Polygons
• Graph theory
• Growing a Tree from Its Branches
• Hamiltonian cycles in planar triangulations with no separating triangles
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• On the perfect matching of disjoint compact sets by noncrossing line segments in \(\mathbb R^n\)

Cited in

(4)

• Visibility in crowds of translates of a centrally symmetric convex body
• The visibility graph of congruent discs is Hamiltonian
• Tight bounds for visibility matching of \(f\)-equal width objects
• On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane

This page was built for publication: On the visibility graph of convex translates

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