6
$\begingroup$

So it's well-known that an alternative way to define a series-parallel (undirected graph) is by the forbidden minor $K_4$. Is there a known analog of this definition for directed graphs — specifically, for DAGs?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

You might want to have a look at the paper

Jacobo Valdes, Robert E. Tarjan, Eugene L. Lawler; The recognition of Series Parallel digraphs; STOC 1979; doi:10.1145/800135.804393

Section 4 is called "Forbidden subgraph characterizations", and it contains the following two statements:

  1. A digraph with a single source and a single sink is a two-terminal series-parallel digraph if and only if it does not contain a subdigraph homeomorphic to the digraph with nodes 1,2,3,4 and arcs (1,2), (1,3), (2,4), (3,4) and (2,3).
  2. A digraph is a general series-parallel digraph if and only if its transitive closure does not contain the digraph with nodes 1,2,3,4 and arcs (1,3), (1,4) and (2,3) as an induced subdigraph.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .