1
$\begingroup$

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.

Thanks.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.