I am looking for some graph theory concepts and definitions around embedding a DAG into another DAG. I could only find a few lines on Wikipedia around this so I wonder if someone can help me find good references for the important concepts and definitions.

For example, assume I have a DAG $G=(E,V)$ where there are two types of edges, red and black. $E_{red} \subset E$, $E_{black} \subset E$, and $E_{red} \cap E_{black} = \emptyset$ .

I assume that the red edges represents some "core" DAG and the black edges represents "details".

If I want to extract this "core" DAG, I might do something like this:

Put $E_{red}$ and all related vertices into a new graph $G' = (E',V')$.

For every pair $e_p,e_c \in E_{red}$, if $e_c$ is reachable from $e_p$ and there is no other $e \in E_{red}$ on the path, then add the edge $(end(e_p),beginning(e_c))$ to $G'$.

$G'$ might then be thought of as having removed the black edges (and thus the details) from $G$.

My question is, what am I doing, and where can I read about embedding DAGs and extracting embeddings based on edge colors?

  • $\begingroup$ I'm not aware of any concept of embedding similar to this; but what you are doing is building an edge-induced subgraph. $\endgroup$ – G. Bach Sep 16 '13 at 16:30
  • $\begingroup$ I added a link to embedding in the question. $\endgroup$ – user239558 Sep 16 '13 at 18:58

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.