Embedding a triangular graph within a given boundary

Yin Xu; Renjie Chen; Craig Gotsman; Ligang Liu

doi:10.1016/j.cagd.2011.07.001

Embedding a triangular graph within a given boundary

Yin Xu, Renjie Chen, Craig Gotsman, Ligang Liu

Research output: Contribution to journal › Article › peer-review

28 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	349-356
Number of pages	8
Journal	Computer Aided Geometric Design
Volume	28
Issue number	6
DOIs	https://doi.org/10.1016/j.cagd.2011.07.001
State	Published - Aug 2011
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Keywords

Embedding
Planar graph
Triangulation

Access to Document

10.1016/j.cagd.2011.07.001

Cite this

@article{06c54e4dc60e4d9a9e3ac4c828e9a230,

title = "Embedding a triangular graph within a given boundary",

abstract = "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.",

keywords = "Embedding, Planar graph, Triangulation",

author = "Yin Xu and Renjie Chen and Craig Gotsman and Ligang Liu",

note = "Funding Information: The work of L. Liu was partially supported by the joint grant of the National Natural Science Foundation of China and Microsoft Research Asia (60776799). R. Chen is partially supported by the Ali Kaufmann postdoctoral fellowship at the Technion.",

year = "2011",

month = aug,

doi = "10.1016/j.cagd.2011.07.001",

language = "English (US)",

volume = "28",

pages = "349--356",

journal = "Computer Aided Geometric Design",

issn = "0167-8396",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Embedding a triangular graph within a given boundary

AU - Xu, Yin

AU - Chen, Renjie

AU - Gotsman, Craig

AU - Liu, Ligang

N1 - Funding Information: The work of L. Liu was partially supported by the joint grant of the National Natural Science Foundation of China and Microsoft Research Asia (60776799). R. Chen is partially supported by the Ali Kaufmann postdoctoral fellowship at the Technion.

PY - 2011/8

Y1 - 2011/8

N2 - 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.

AB - 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.

KW - Embedding

KW - Planar graph

KW - Triangulation

UR - https://www.scopus.com/pages/publications/80051959748

UR - https://www.scopus.com/inward/citedby.url?scp=80051959748&partnerID=8YFLogxK

U2 - 10.1016/j.cagd.2011.07.001

DO - 10.1016/j.cagd.2011.07.001

M3 - Article

AN - SCOPUS:80051959748

SN - 0167-8396

VL - 28

SP - 349

EP - 356

JO - Computer Aided Geometric Design

JF - Computer Aided Geometric Design

IS - 6

ER -

Embedding a triangular graph within a given boundary

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this