A recursive implementation of the EmbedBranch function, as defined on pages 8 and 22 of the paper.

def __embed_branch_recursive(u, dfs_data):
    """A recursive implementation of the EmbedBranch function, as defined on pages 8 and 22 of the paper."""
    #print "\nu: {}\nadj: {}".format(u, dfs_data['adj'][u])

    #print 'Pre-inserts'
    #print "FG: {}".format(dfs_data['FG'])
    #print "LF: {}".format(dfs_data['LF'])
    #print "RF: {}".format(dfs_data['RF'])

    for v in dfs_data['adj'][u]:
        #print "\nu, v: {}, {}".format(u, v)
        #print "dfs_u, dfs_v: {}, {}".format(D(u, dfs_data), D(v, dfs_data))
        nonplanar = True
        if a(v, dfs_data) == u:
            #print 'Ancestor block entered:', u, v
            if b(v, dfs_data) == u:
                successful = __insert_branch(u, v, dfs_data)
                if not successful:
                    #print 'InsertBranch({}, {}) Failed'.format(u, v)
                    nonplanar = True
                    return nonplanar
            nonplanar = __embed_branch_recursive(v, dfs_data)
            if nonplanar:
                return nonplanar
        elif is_frond(u, v, dfs_data):
            #print 'Frond block entered:', u, v
            successful = __embed_frond(u, v, dfs_data)
            if not successful:
                #print 'EmbedFrond({}, {}) Failed'.format(u, v)
                nonplanar = True
                return nonplanar

            #print 'Post EmbedFrond'
            #print "FG: {}".format(dfs_data['FG'])
            #print "LF: {}".format(dfs_data['LF'])
            #print "RF: {}".format(dfs_data['RF'])
        else:
            # This block is totally valid, and there will be multiple cases when it gets hit.
            # We only want to do things if an edge is a tree edge (parent to child along the spine of the DFS tree),
            # or if it's a frond edge (an edge moving up the tree from lower along the spine).
            # Every non-tree edge will eventually get handled by the frond edge code as we recurse up the spine.
            pass
    #print "{}: Should be planar".format(u)

    #print 'Post-inserts'
    #print "FG: {}".format(dfs_data['FG'])
    #print "LF: {}".format(dfs_data['LF'])
    #print "RF: {}".format(dfs_data['RF'])

    nonplanar = False
    return nonplanar