I am trying to understand if a planarity check algorithm (eg. LR Planarity, PC Tree, PQ Tree, etc...) can be enhanced such that some edges are allowed to cross depending on their type.
I have a graph with edges of 3 different types: A,B,C
Edges of type A cannot cross any other edges.
Edges of type B can cross edges of type C and vice versa.
I did already look at a simple LR planarity test, but could not successfully implement this feature.
Is it possible to take an existing algorithm and adjust it with these rules, or is there already an algorithm, which supports this?
Take the sub-graph containing only the type A edges and use a standard planarity testing algorithm to see if it is planar.
Note: one graph may generate multiple planar embeddings [page 60] so you may need to account for this.
Once you have a planar embedding for the type A edges then you can generate a list of faces.
A path of type B edges that connects from two vertices in the planar sub-graph generated by the type A edges can only be drawn in a planar manner (not crossing any type A edges) if the end-points of the path are both on the boundary of a single face of the embedding. Adding this to the embedding will, by the Jordan Curve theorem, bisect the face into which the embedding was performed and generate two sub-faces.
Note: again, a path may be able to bisect multiple faces so you may have multiple potential embeddings.
Continue performing embeddings of type B edges/paths which connect at both ends to the type A sub-graph and, at each step bisecting a face until you either reach a point where there is no viable face to bisect (and the graph is non-planar) or the type A and type B edges are planar.
Since type C edges can cross type B (and vice-versa) you can embed the type C edges (using the same method of face bisection) into the type A sub-graph without considering the type B edges (since they can be crossed).
While this can be done in O(N) for type A and either B or C (since that is effectively just an ordinary planar embedding), you may have to test multiple embeddings to find an orientation of the faces which works for A, B & C together and the resulting algorithm will almost certainly not be O(N).
Alternatively, if you know the constraints on the permutations of the faces when generating different embeddings then adding in some sort of constraint-based solver to reconcile the orientation of the paths in the embedding may assist.