What is the name of this graph-theoretic construction?

55 Views Asked by At

I have been thinking about a graph-theoretic construction and was wondering if anyone knew what it was called.

I suspect that this is a construction that is

  • already named or closely related to a named construction; and
  • valid for all directed acyclic graphs (DAGs).

I'll give an example first and then try to formulate the construction.

Original DAG

Directed acyclic graph (original)

Constructed DAG

Directed acyclic graph (after construction)

Nonrigorous description of construction

Below is a description of the construction I am asking about.

Given a DAG, the construction (vaguely) consists of

  1. possibly adding one or more new vertices (in the example above, the vertex $X$)

  2. possibly modifying the edges such that

    1. the constructed graph is still a DAG
    2. reachability and non-reachability between all original vertices are preserved
    3. the underlying undirected graph of the constructed DAG is a tree (unsure about this one — as @Dániel G. points out, this would be impossible if, say, the subgraph of reachable vertices from some vertex in the original DAG contained a cycle in its underlying graph)

I have not verified that this construction is well-defined (existent/unique) for all DAGs.

The motivation is, in the context where a directed edge from a vertex points to a direct ancestor or a direct dependency, abstracting/inferring "hidden" ancestors or dependencies that "simplify" the overall ancestry or dependence structure.

Related concepts

Based on my search so far, I suspect these concepts may be related to my construction as (vaguely) described above.

  1. polytree
  2. semilattice