On the visibility graph of convex translates

DOI10.1016/S0166-218X(00)00270-5zbMATH Open1003.68114MaRDI QIDQ5951963FDOQ5951963

Authors: Kiyoshi Hosono, Henk Meijer, David Rappaport 

Publication date: 28 October 2002

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

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

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)

Cites Work

• Graph theory
• Computational Geometry in C
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hamiltonian cycles in planar triangulations with no separating triangles
• Convex Polygons
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Growing a Tree from Its Branches
• 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
• Tight bounds for visibility matching of \(f\)-equal width objects
• The visibility graph of congruent discs is Hamiltonian
• 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)