Graph-theoretical conditions for inscribability and Delaunay realizability

DOI10.1016/0012-365X(95)00276-3zbMath0870.05048OpenAlexW1966798156MaRDI QIDQ1356410

Warren D. Smith, Michael B. Dillencourt

Publication date: 15 September 1997

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

Full work available at URL: https://doi.org/10.1016/0012-365x(95)00276-3

zbMATH Keywords

HamiltonianpolyhedronmatchingsDelaunay triangulationsinscribable type

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items

About \(f\)-vectors of inscribed simplicial polytopes, Outerplanar Graphs and Delaunay Triangulations, Anchored expansion, speed and the Poisson-Voronoi tessellation in symmetric spaces, Finding Hamiltonian cycles in Delaunay triangulations is NP-complete, Characterizing proximity trees, A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere, Scaffolding skeletons using spherical Voronoi diagrams, The rectangle of influence drawability problem, Realizability and inscribability for simplicial polytopes via nonlinear optimization, COMBINATORIAL INSCRIBABILITY OBSTRUCTIONS FOR HIGHER DIMENSIONAL POLYTOPES, Computational complexity of the vertex cover problem in the class of planar triangulations, Limits of local search: quality and efficiency, Witness (Delaunay) graphs, Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces, Intersection number and stability of some inscribable graphs, Six Topics on Inscribable Polytopes, Weakly inscribed polyhedra, Voronoi drawings of trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Toughness and Delaunay triangulations
• Realizability of Delaunay triangulations
• Matching theory
• Voronoi diagrams from convex hulls
• Note on inscribability of quadrangular polyhedra with restricted number of edge-types
• Planar and infinite hypohamiltonian and hypotraceable graphs
• Bridges and Hamiltonian circuits in planar graphs
• 4-connected projective planar graphs are Hamiltonian
• Some problems on polyhedra
• A characterization of ideal polyhedra in hyperbolic 3-space
• Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
• Hamiltonian circuits in simplicial complexes
• On geometry of convex ideal polyhedra in hyperbolic 3-space
• Tough graphs and Hamiltonian circuits.
• Shortness exponents of families of graphs
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• A Theorem on Planar Graphs
• A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
• A simple method for resolving degeneracies in Delaunay triangulations
• A LINEAR-TIME ALGORITHM FOR TESTING THE INSCRIBABILITY OF TRIVALENT POLYHEDRA
• The Factorization of Linear Graphs
• A theorem on paths in planar graphs