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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.