Embeds a frond uw into either LF or RF. Returns whether the embedding was successful.

def __embed_frond(node_u, node_w, dfs_data, as_branch_marker=False):
    """Embeds a frond uw into either LF or RF. Returns whether the embedding was successful."""
    d_u = D(node_u, dfs_data)
    d_w = D(node_w, dfs_data)

    comp_d_w = abs(d_w)
    if as_branch_marker:
        d_w *= -1
        if dfs_data['last_inserted_side'] == 'LF':
            __insert_frond_RF(d_w, d_u, dfs_data)
        else:
            # We default to inserting a branch marker on the left side, unless we know otherwise
            __insert_frond_LF(d_w, d_u, dfs_data)
        return True

    LF = dfs_data['LF']
    m = dfs_data['FG']['m']
    l_w = lw(dfs_data)
    r_w = rw(dfs_data)
    u_m = u(m, dfs_data)
    x_m = fn_x(m, dfs_data)

    # There are multiple cases for both u and w
    # --Detect the case for u and store it for handling once the case for w is determined
    case_1 = False
    case_2 = False
    case_3 = False

    if d_u > u_m and d_u > x_m:
        case_1 = True
    elif d_u <= u_m and d_u > x_m:
        case_2 = True
    elif d_u > u_m and d_u <= x_m:
        case_3 = True
    else:
        # We should never get here, return false because there's no way we can embed this frond
        #print "Invalid u-case detected: (d_u, u_m, x_m): ({}, {}, {})".format(d_u, u_m, x_m)
        #print "FG: {}".format(dfs_data['FG'])
        #print "LF: {}".format(dfs_data['LF'])
        #print "RF: {}".format(dfs_data['RF'])
        return False

    # --Detect the case for w and process the edge appropriately
    if comp_d_w >= l_w and comp_d_w >= r_w:
        # Case 4
        #print "w-case 4 reached"
        # --We do the same thing for all three u-cases: Add the frond to the left side
        __insert_frond_LF(d_w, d_u, dfs_data)

        dfs_data['FG']['m'] += 1
        m = dfs_data['FG']['m']
        n = dfs_data['graph'].num_nodes()

        Lm = {'u': d_w, 'v': d_u}
        Rm = {'x': n, 'y': 0} # See page 17 for how we deal with Ri being empty
        #Rm = {}
        dfs_data['FG'][m] = [Lm, Rm]
        return True
    elif comp_d_w >= l_w and comp_d_w < r_w:
        # Case 5
        #print "w-case 5 reached"
        return __do_case_5_work(d_w, d_u, case_1, case_2, case_3, dfs_data)
    elif comp_d_w < l_w and comp_d_w >= r_w:
        # Case 6
        #print "w-case 6 reached"
        return __do_case_6_work(d_w, d_u, case_1, case_2, case_3, dfs_data)
    elif comp_d_w < l_w and comp_d_w < r_w:
        # Case 7
        #print "w-case 7 reached"
        #print "FG: {}".format(dfs_data['FG'])
        #print "LF: {}".format(dfs_data['LF'])
        #print "RF: {}".format(dfs_data['RF'])
        #print "(d_w, l_w, r_w): ({}, {}, {})".format(d_w, l_w, r_w)
        #print "(d_u, u_m, x_m, m): ({}, {}, {}, {})".format(d_u, u_m, x_m, m)
        while comp_d_w < l_w and comp_d_w < r_w:
            if d_u > u_m and d_u > x_m:
                #print "Nonplanar case reached: u-case 1, w-case 7"
                #print "FG: {}".format(dfs_data['FG'])
                #print "LF: {}".format(dfs_data['LF'])
                #print "RF: {}".format(dfs_data['RF'])
                #print "(d_w, l_w, r_w): ({}, {}, {})".format(d_w, l_w, r_w)
                #print "(d_u, u_m, x_m, m): ({}, {}, {}, {})".format(d_u, u_m, x_m, m)
                return False
            switch_sides(d_u, dfs_data)

            # --Update the local variables fo the next loop iteration
            l_w = lw(dfs_data)
            r_w = rw(dfs_data)
            m = dfs_data['FG']['m']
            u_m = u(m, dfs_data)
            x_m = fn_x(m, dfs_data)

        case_1 = False
        case_2 = False
        case_3 = False
        if d_u <= u_m and d_u > x_m:
            case_2 = True
        elif d_u > u_m and d_u <= x_m:
            case_3 = True

        if comp_d_w >= l_w and comp_d_w < r_w:
            # Case 5 redux
            #print "w-case 5 redux reached"
            return __do_case_5_work(d_w, d_u, case_1, case_2, case_3, dfs_data)
        if comp_d_w < l_w and comp_d_w >= r_w:
            # Case 6 redux
            #print "w-case 6 redux reached"
            return __do_case_6_work(d_w, d_u, case_1, case_2, case_3, dfs_data)
    else:
        # We should never get here, return false because there's no way we can embed this frond
        #print "Invalid w-case detected"
        return False

    # We really shouldn't get to this point, but this is a catch-all just in case
    #print "Failure catchall reached"
    return False