Braced Edges in Plane Triangulations

Eggleton, Roger B. and MacDougall, James A. and Al-Hakim, Latif A. (1990) Braced Edges in Plane Triangulations. Australasian Journal Combinatorics, 2 . pp. 121-134.

PDF - Accepted Version
Download (1226Kb) | Preview


    A plane triangulation is an embedding of a maximal planar graph in the Euclidean plane. Foulds and Robinson (1979) first studied the problem of transforming one triangulation to another by a sequence of diagonal operations, where a diagonal operation deletes one edge and inserts the other diagonal of the resulting quadrilateral face. An edge which cannot be removed by a single diagonal operation is called braced. This paper is a study of the possible number and distribution of braced edges in a triangulation. It shows that at most $2n-4$ edges of a triangulation of order $n$ can be braced, and that for any $r \leq 2n-4$ (with exactly one exception) there is a plane triangulation of order $n$ with $r$ braced edges, so long as $n$ is large enough.

    Item Type: Article
    Subjects: 00-xx General
    Faculty: UNSPECIFIED
    Depositing User: Stephanie
    Date Deposited: 18 Nov 2010 12:06
    Last Modified: 13 Mar 2012 14:42

    Actions (login required)

    View Item