In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class.
What about Poly-trees (oriented trees)? These are DAG's where the possible paths from a node are all trees. Unlike trees, Poly-tree nodes can have several 'parents'.
Are polytrees in the same sub-graph isomorphism complexity class of DAG's or are there known polynomial-time algorithms for sub-polytree isomorphism?
From the definition of planar graphs - that you can always draw them on plane in such a way that edges just meet on nodes - I believe all polytrees are planar graphs (please correct me if I am wrong).
Now since subgraph isomorphism of planar graphs has polinomial time algorithms available, I guess Sub-Polytrees isomorphism is also in the polynomial time complexity class.