I wonder if there exist definitions (and known algorithms) of planarity testing for the following case:

1- A directed graph

let $G=(V=\{1,\ldots,n\},E)$ be a directed graph.

Assume $e_{ij} =(v_i,v_j), e_{ji} = (v_j,v_i)$ are two unique edges.

I'm looking for a known (similar) definitions for this kind of planarity testing that forbids any of the above combinations for $1\leq i<j \leq n$.

2- A 3d grid

Assume our graph is embedd in a 3d grid, where each point the grid has the following structure: $(i,j,k)$, where w.l.o.g $1\leq i<j<k \leq n$. And the edges must be "straight" (in the 3d-world).

I'm asking whether it is known a problem and there are known planarity testing algorithms for this kind of problem.




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.