Toughness and Delaunay triangulations

DOI10.1007/BF02187810zbMath0727.05040OpenAlexW2118927049MaRDI QIDQ803161

Michael B. Dillencourt

Publication date: 1990

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131137

zbMATH Keywords

polytopesDelaunay triangulationperfect matchings1-toughnessinterior component

Mathematics Subject Classification ID

Other problems of combinatorial convexity (52A37) Eulerian and Hamiltonian graphs (05C45)

Related Items (27)

Simpler proof of a realizability theorem on Delaunay triangulations ⋮ Triangulations without minimum-weight drawing ⋮ PROXIMITY GRAPHS: E, δ, Δ, χ AND ω ⋮ 2-change for k-connected networks ⋮ Graph-theoretical conditions for inscribability and Delaunay realizability ⋮ Maximum and minimum toughness of graphs of small genus ⋮ Unnamed Item ⋮ Finding Hamiltonian cycles in Delaunay triangulations is NP-complete ⋮ Disjoint empty disks supported by a point set ⋮ A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere ⋮ Matchings in 1‐planar graphs with large minimum degree ⋮ Strong matching of points with geometric shapes ⋮ Higher-order triangular-distance Delaunay graphs: graph-theoretical properties ⋮ Approximate proximity drawings ⋮ A simple method for resolving degeneracies in Delaunay triangulations ⋮ Matching points with rectangles and squares ⋮ Witness (Delaunay) graphs ⋮ Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces ⋮ The drawability problem for minimum weight triangulations ⋮ Matching points with squares ⋮ Hamiltonicity for convex shape Delaunay and Gabriel graphs ⋮ Affine invariant triangulations ⋮ Six Topics on Inscribable Polytopes ⋮ ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS ⋮ An upper bound on the shortness exponent of 1-tough, maximal planar graphs ⋮ Voronoi drawings of trees ⋮ Matchings in higher-order Gabriel graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• On sorting triangles in a Delaunay tessellation
• An upper bound on the shortness exponent of 1-tough, maximal planar graphs
• Realizability of Delaunay triangulations
• Recognizing tough graphs is NP-hard
• Traveling salesman cycles are not always subgraphs of Voronoi duals
• Recognizing Dirichlet tesselations
• On the average length of Delaunay triangulations
• The greedy and Delaunay triangulations are not bad in the average case
• Generalized Dirichlet tesselations
• Voronoi diagrams and arrangements
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• Some problems in computational geometry
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• An upper bound on the shortness exponent of inscribable polytopes
• Voronoi diagrams from convex hulls
• A 1-tough nonhamiltonian maximal planar graph
• A note on Delaunay and optimal triangulations
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• A theorem on graphs
• Some problems on polyhedra
• Tough graphs and Hamiltonian circuits.
• Connect-the-dots: A new heuristic
• Hamiltonian circuits on 3-polytopes
• The Factorization of Linear Graphs

This page was built for publication: Toughness and Delaunay triangulations