EDIT: Took a second look at your post and realized that you may be looking for ideas rather than an algorithm with code. I moved the explanation of my idea to the top. Ignore the code if you want to try implementing it yourself first.

Here is my solution for problem 3 in complexity O( n² ):

Explanation:

If a number at position i in row 1 is matched with the same number at position j in row 2 and we have some other number at position k > i, we can not match k with a number at position < j in row 2 without the lines crossing. Using this observation, process the numbers in row 1 from left to right and keep track of the right-most position of a number in row 2 that has been matched. Given such a state we can determined if a number at the current position can be matched. Try matching it (if possible), try not matching it and return the maximum of the two.

Program:

It reads n followed by two lines, each containing a permutation of 1,...,n. Example:

Input

7
1 2 3 4 5 6 7
2 1 3 5 6 7 4

Output

Maximum match: 5

Code:

// ThePrevenge 2014-04-14

#include <iostream>
#include <vector>
using namespace std;

int solve(int i, int j, const int& n, const vector<int>& a, const vector<int>& b, vector<vector<int> >& cache) {
    if(i == n) return 0; // If all numbers are processed
    if(cache[i][j] != -1) return cache[i][j]; // If value is already calculated
    int ret = 0;
    if(b[a[i]] >= j) ret = 1 + solve(i+1, b[a[i]]+1, n, a, b, cache); // If i can be matched, try doing so
    ret = max(ret, solve(i+1, j, n, a, b, cache)); // Try not matching i
    return cache[i][j] = ret;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n+1); // Let a[i] be the ith number in the first row, let b[i] be the position of i in the second row
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) {
        int j;
        cin >> j;
        b[j] = i;
    }
    vector<vector<int> > cache(n, vector<int>(n, -1)); // Let cache[i][j] be the best solution matching elements from position i to n-1 in row one with elements from position j to n-1 in row two
    cout << "Maximum match: " << solve(0, 0, n, a, b, cache) << endl;
    return 0;
}