def _triangulate(g, comb_emb):
    """
    Helper function to schnyder method for computing coordinates in the plane to
    plot a planar graph with no edge crossings.

    Given a connected graph g with at least 3 vertices and a planar combinatorial
    embedding comb_emb of g, modify g in place to form a graph whose faces are
    all triangles, and return the set of newly created edges. Also ``comb_emb``
    is updated in place.

    The simple way to triangulate a face is to just pick a vertex and draw
    an edge from that vertex to every other vertex in the face. Think that this
    might ultimately result in graphs that don't look very nice when we draw them
    so we have decided on a different strategy.  After handling special cases,
    we add an edge to connect every third vertex on each face.  If this edge is
    a repeat, we keep the first edge of the face and retry the process at the next
    edge in the face list.  (By removing the special cases we guarantee that this
    method will work on one of these attempts.)

    INPUT:

    - g -- the graph to triangulate
    - ``comb_emb`` -- a planar combinatorial embedding of g

    OUTPUT:

    A list of edges that are added to the graph (in place)

    EXAMPLES::

        sage: from sage.graphs.schnyder import _triangulate
        sage: g = Graph(graphs.CycleGraph(4))
        sage: g.is_planar(set_embedding=True)
        True
        sage: _triangulate(g, g._embedding)
        [(2, 0), (1, 3)]

        sage: g = graphs.PathGraph(3)
        sage: g.is_planar(set_embedding=True)
        True
        sage: new_edges = _triangulate(g, g._embedding)
        sage: [sorted(e) for e in new_edges]
        [[0, 2]]
    """
    # first make sure that the graph has at least 3 vertices, and that it is connected
    if g.order() < 3:
        raise ValueError("A Graph with less than 3 vertices doesn't have any triangulation.")
    if not g.is_connected():
        raise NotImplementedError("_triangulate() only knows how to handle connected graphs.")

    # At this point we know that the graph is connected, has at least 3
    # vertices. This is where the real work starts.

    faces = g.faces(comb_emb)
    # We start by finding all of the faces of this embedding.

    edges_added = []   # The list of edges that we add to the graph.
    # This will be returned at the end.

    for face in faces:
        new_face = []
        if len(face) < 3:
            raise RuntimeError('Triangulate method created face %s with < 3 edges.' % face)
        if len(face) == 3:
            continue  # This face is already triangulated
        elif len(face) == 4:  # In this special case just add diagonal edge to square
            u, v, w, x = (e[0] for e in face)
            if w == u or g.has_edge(w,u):
                u, v, w, x = v, w, x, u
            new_face = (w, u)
            comb_emb[w].insert(comb_emb[w].index(x), u)
            comb_emb[u].insert(comb_emb[u].index(v), w)
            g.add_edge(new_face)
            edges_added.append(new_face)
        else:
            N = len(face)
            i = 0
            while i < N - 1:
                new_edge = (face[i + 1][1], face[i][0])  # new_edge is from third vertex in face to first
                if g.has_edge(new_edge) or new_edge[0] == new_edge[1]:  # check for repeats
                    new_face.append(face[i])  # if repeated, keep first edge in face instead
                    if i == N - 2:   # if we are two from the end, found a triangle already
                        break
                    i += 1
                    continue

                g.add_edge(new_edge)
                edges_added.append(new_edge)
                comb_emb[new_edge[0]].insert(comb_emb[new_edge[0]].index((face + new_face)[i + 2][1]), new_edge[1])
                comb_emb[new_edge[1]].insert(comb_emb[new_edge[1]].index(face[i][1]), new_edge[0])
                new_face.append((new_edge[1], new_edge[0]))
                i += 2
            if i != N:
                new_face.append(face[-1])
            faces.append(new_face)

    return edges_added