BF-graph

Each blue hyperedge has all tails but one, making them B-arcs. Likewise, each orange edge has all heads but one, making them F-arcs. A BF-graph consists only of these two kinds of directed arcs, such as the one shown.

In graph theory, a BF-graph is a type of directed hypergraph where each hyperedge is directed either to one particular vertex or away from one particular vertex.

Definition

In a directed hypergraph, each hyperedge may be directed away from some of its vertices (its tails) and towards some others of its vertices (its heads). A hyperedge that is directed to a single head vertex, and away from all its other vertices, is called a B-arc (backward arc). Symmetrically, a hyperedge that is directed away from a single tail vertex, and towards all its other vertices, is called an F-arc (forward arc).

A hypergraph with only B-arcs is a B-graph (or B-hypergraph) and a hypergraph with only F-arcs is a F-graph (or F-hypergraph). A BF-graph (or BF-hypergraph) is a hypergraph whose hyperarcs are either B-arcs or F-arcs.

Properties

Any general directed hypergraph can be transformed into a BF-graph by adding a dummy node to each hyperarc that is neither a B-arc nor an F-arc, thus replacing each such hyperarc with one B-arc and one F-arc.

The symmetric image of a B-graph is an F-graph, and vice versa. This is obtained by reversing the direction of all hyperarcs.

Paths and connectivity

In BF-graphs, different types of paths and connectivity can be defined:

• A B-path (or B-hyperpath) from node s to node t is a minimal hypergraph where every node is connected to s by means of a cycle-free simple path
• An F-path (or F-hyperpath) from s to t is a hypergraph whose symmetric image is a B-path from t to s
• A BF-path (or BF-hyperpath) from s to t is a hypergraph that is simultaneously both a B-path and an F-path from s to t

Correspondingly, nodes can be B-connected, F-connected, or BF-connected depending on whether the respective type of path exists between them.

Applications

Directed hypergraphs and their BF-graph subfamily have found applications across diverse areas of computer science, including database systems, expert systems, parallel programming, scheduling, routing in dynamic networks, data mining, and bioinformatics.

B-graphs

B-graphs have been particularly useful in representing Horn formulae in propositional logic, where they are sometimes called "labelled graphs". They have also been applied to analyzing deductive databases and studying Leontiev substitution matrices and flow problems.

F-graphs

F-graphs have found applications in urban transit problems, particularly for modeling passenger distribution in transit systems. They have also been used in the analysis of And-Or graphs in artificial intelligence.

BF-graphs

BF-graphs provide a general framework that can model concurrent systems and parallel computation programs. They are particularly useful for representing task precedence and simultaneous execution in synchronous systems. The structure has also been applied to scheduling problems and routing in dynamic networks.

BF-graphs are well-suited for representing functional dependencies in relational databases, as both the domain and codomain of a functional dependency may contain multiple attributes. This property has been utilized in converting relational databases to Resource Description Framework (RDF) representations for semantic web applications.

Computational complexity

Several path problems that are polynomial-time solvable on ordinary directed graphs become NP-hard when extended to BF-graphs. For example, finding a minimum cardinality B-path in a B-graph is NP-hard, even though the corresponding shortest path problem in ordinary graphs can be solved in polynomial time. However, certain special cases and constrained versions of these problems remain tractable.

In contrast, planarity testing for BF-graphs can be performed efficiently in linear time with respect to the size of the hypergraph.

See also

• Hypergraph
• Directed graph
• Graph planarity