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

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

• 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
• 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