Skip to main navigation Skip to search Skip to main content

Does contraction preserve triangular meshes?

Research output: Contribution to journalArticlepeer-review

Abstract

A triangular graph is a planar graph in which each face is a 3-cycle, except possibly for the exterior face, and without articulation nodes. The embedding of a triangular graph in the plane is called a triangular mesh. More generally, a triangular graph with multiple contours is a planar graph without articulation nodes in which each face is a 3-cycle, except possibly for a fixed number of them. A contraction along an edge in a graph is the result of identifying the two endpoints of the edge. In this paper a necessary and sufficient condition is shown for which triangularity (possibly with multiple contours) is preserved after contraction. Moreover, when a licit contraction is performed, the question to answer is whether or not it is possible to derive the embedding of the contracted triangular graph from the original triangular mesh by redrawing only around the contraction zone.

Original languageEnglish
Pages (from-to)201-223
Number of pages23
JournalNumerical Algorithms
Volume13
Issue number2
DOIs
Publication statusPublished - 1 Jan 1996
Externally publishedYes

Fingerprint

Dive into the research topics of 'Does contraction preserve triangular meshes?'. Together they form a unique fingerprint.

Cite this