Embedding a triangular graph within a given boundary

DOI10.1016/J.CAGD.2011.07.001MaRDI QIDQ654561zbMATH OpenOpenAlexFDO

Authors Yin Xu, Renjie Chen, Craig Gotsman, Ligang Liu

Publication date 29 December 2011

Published in Computer Aided Geometric Design (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cagd.2011.07.001

zbMATH Keywords

algorithmembeddingplanar graphtriangulation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Computer-aided design (modeling of curves and surfaces) (65D17) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

Given a 3-vertex-connected triangular planar graph and an embedding of its boundary vertices, can the interior vertices be embedded to form a valid triangulation? An algorithm which decides this problem and produces such an embedding if it exists, or reject the input in case no valid embedding exists is described in this article. Experimental results demonstrate the effectiveness of the introduced algorithm.

Recommendations

• On triangulating planar graphs under the four-connectivity constraint
• Planar Embeddings of Graphs with Specified Edge Lengths
• On triangulating planar graphs under the four-connectivity constraint
• scientific article; zbMATH DE number 1500680
• Does contraction preserve triangular meshes?

Cites work

• Computing Discrete Minimal Surfaces and Their Conjugates
• Convex combination maps over triangulations, tilings, and tetrahedral meshes
• Convex Drawings of Graphs with Non-convex Boundary
• How to Draw a Graph
• Parametrization and smooth approximation of surface triangulations
• Tutte's barycenter method applied to isotopies
• Volumetric harmonic map

Cited in

(6)

• Restricted triangulation on circulant graphs
• On inversion-free mapping and distortion minimization
• Surface segmentation for polycube construction based on generalized centroidal Voronoi tessellation
• Centroidal Voronoi tessellation based polycube construction for adaptive all-hexahedral mesh generation
• A Novel Algorithm for Volume-Preserving Parameterizations of 3-Manifolds
• Does contraction preserve triangular meshes?

This page was built for publication: Embedding a triangular graph within a given boundary

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