Embedding a triangular graph within a given boundary

Yin Xu, Renjie Chen, Craig Gotsman, Ligang Liu

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


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? We describe an algorithm which decides this problem and produces such an embedding if it exists.

Original languageEnglish (US)
Pages (from-to)349-356
Number of pages8
JournalComputer Aided Geometric Design
Issue number6
StatePublished - Aug 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design


  • Embedding
  • Planar graph
  • Triangulation


Dive into the research topics of 'Embedding a triangular graph within a given boundary'. Together they form a unique fingerprint.

Cite this