The **line digraph** *L(D)* of a digraph *D*
is the
intersection digraph
of the arc set of *D*,
where an arc is viewed as a pair of vertices.
Line digraphs are generally considered as the
natural digraph analogue of
line graphs.
However, recognizing line digraphs is considerably
easier than recognizing line graphs---if we do not have loops,
we simply have to find all so-called
dicliques and
essentially
compute its intersection digraph to find *D*.
There is no ambiguity, as for line graphs, where we have
to find out which triangles are star graphs.
If we look closer on the concept, line digraphs are not the analogue
of line graphs---instead, they are digraph analogues of unions of
complete graphs.
Interval digraphs of multigraphs are just intersection digraphs of
families of pairs *(S _{x},T_{x})*,
where each

Intersection bigraphs of pairs of 1-element sets are just unions of
complete bipartite graphs. In other words, a digraph *D* is the
line digraph of some multigraph iff its bigraph *B(D)*
is the disjoint union of complete bipartite graphs.

What about discrete intersection bigraph models
where the sets involved are larger?
Intersection bigraphs of families
*((S _{x},T_{x}),
xV)*,
where the

Thus the first challenge, and the real bigraph version
of line graphs, would be the case where all
*S _{x}* and all

Obviously all
star graphs are complete bipartite,
but not all of them are
bicliques.
On the other hand, there are several other types
of bicliques in *B*,
as indicated below:

It turns out that the recognition problem is easy
if we require large enough minimum degree on both
*G _{1}* and

Under the condition
*(G _{1}),
(G_{2})4*,
all star graphs are bicliques, and more important,
all bicliques are star graphs.
Then recognition is straightforward.

Let us now relax to the condition
*(G _{1}),
(G_{2})3*.
Again all star graphs are bicliques, and there are only two further
types of bicliques, type 3 and type 4 in the
figure above.
Note that every vertex of

If *B* is indeed a line bigraph with
*G _{1}, G_{2}* as above,
and if our assumption on

[P°]:
There is a polynomial-time algorithm that decides for any
bipartite graph
B whether it is the line bigraph
of a pair (G
of graphs on the same vertex set, with
_{1},G_{2})(G.
_{1}),
(G_{2})3 |

Recognizing *general* line bigraphs
is however NP-complete [P°].

Do you want to visit also interval bigraphs, or go back to the start page for intersection graphs?

Erich Prisner

made on January 12, 1999