Classes of Directed Graphs

In this chapter we will provide most of the terminology and notation used in this book. Various examples, figures and results should help the reader to better understand the notions introduced in the chapter. We also prove some basic results on digraphs and provide some fundamental digraph results without proofs. Most of our terminology and notation is standard and agrees with (Bang-Jensen, Gutin, Digraphs: theory, algorithms and applications. Springer, London, 2009, [4]).

The class of tournaments is by far the most well-studied class of digraphs with many deep and important results. Since Moon’s pioneering book in 1968 [146], the study of tournaments and their properties has flourished and research on tournaments is still a very active area. Often this research deals with the superclass of semicomplete digraphs which are digraphs with no pair of non-adjacent vertices (that is, contrary to tournaments, we allow directed cycles of length 2). In this chapter we cover a very broad range of results on tournaments and semicomplete digraphs from classical to very recent ones. In order to stimulate further research, we not only list a number of open problems, but also give a number of proofs which illustrate the diversity of proof techniques that have been applied. These range from elementary to quite advanced.

An Euler digraph is a connected digraph where every vertex has in-degree equal to its out-degree, named after the classical result that a digraph admits an Euler tour—i.e., a tour visiting every arc exactly once—if and only if it is an Euler digraph. For many problems, Euler digraphs form a class of intermediate complexity between undirected graphs and general digraphs, allowing for algorithmic results that are not possible in general digraphs while being more expressive than undirected graphs. In addition, remarkably, there are a few problems (including counting Euler tours, and the Arc Multiway Cut problem) where Euler digraphs allow polynomial-time algorithms for problems that are intractable even on undirected Euler graphs. In this chapter, we review some properties of Euler digraphs, and survey algorithmic results according to the above.

In this chapter we focus on planar directed graphs, that is, directed graphs that can be drawn on a plane (or, equivalently, on a sphere) without arc crossings. The main goal of this chapter is to show, from multiple angles, how the planarity assumption imposes structure on digraphs and how such structure, in conjunction with topological arguments, can be used algorithmically.

The class of locally semicomplete digraphs was discovered by Bang-Jensen in 1988. Locally semicomplete digraphs form a significant generalization of semicomplete digraphs with a very rich structure. The class contains digraphs, such as directed cycles, that are very far from being semicomplete. Yet a large number of classical results for semicomplete digraphs still hold for locally semicomplete digraphs. Two examples are that every connected locally semicomplete digraph is traceable and every strongly connected locally semicomplete digraph has a hamiltonian cycle. Since Bang-Jensen’s paper (J. Graph Theory, 14(3):371–390, 1990, [9]) was published in 1990 there has been a significant amount of research done on the class including several PhD theses. In this chapter we survey a number of important results, both structural and algorithmic, on locally semicomplete digraphs and illustrate various important proof-techniques. Several of the results hold even for some superclasses of locally semicomplete digraphs. Many of the proofs and algorithms rely on a structural characterization of those locally semicomplete digraphs that are not semicomplete (have independence number at least 2). As it turns out, these digraphs fall in two disjoint classes, called round decomposable and evil locally semicomplete digraphs, respectively. The first of these has a structure which allows many problems to be solved efficiently, whereas the second class, the evil locally semicomplete digraphs, has a structure which is much closer to that of semicomplete digraphs and hence requires much more work for many problems.

In this chapter we will consider the class of semicomplete multipartite digraphs (SMD). A digraph is semicomplete multipartite if it is obtained from a complete multipartite graph by replacing every edge by an arc or a pair of opposite arcs. In other words, the vertex set of a semicomplete multipartite digraph can be partitioned into sets such that vertices within the same set are nonadjacent and vertices between different sets are adjacent. This chapter gives a comprehensive survey on this class of digraphs.

A digraph D is quasi-transitive if for any three distinct vertices x, y, z in D, the existence of the arcs xy and yz in D implies that xz, zx or both are arcs of D. Quasi-transitive digraphs generalize both tournaments (and semicomplete digraphs) and transitive digraphs, and share some of the nice properties of these families. In particular, many problems that are \(\mathcal {NP}\)-complete for general digraphs become solvable in polynomial time when restricted to quasi-transitive digraphs. In this chapter, we focus on presenting how usually difficult problems admit efficient solutions for the family of quasi-transitive digraphs and some of its generalizations. We begin with the study of the structure of quasi-transitive digraphs, given by the recursive characterization theorem known as the Canonical Decomposition Theorem; two generalizations of quasi-transitive digraphs are introduced. We define a digraph D to be k-quasi-transitive if for any pair of vertices x, y in D, the existence of a path of length k from x to y implies that xy, yx or both are arcs of D. Given a class of digraphs \(\varPhi \), we say that a digraph is totally \(\varPhi \)-decomposable if it can be expressed as a composition of totally \(\varPhi \)-decomposable digraphs; this concept generalizes the structure of quasi-transitive digraphs given by the Canonical Decomposition Theorem. Some of the problems studied for quasi-transitive digraphs and its generalizations include hamiltonicity, traceability, k-linkages weak k-linkages, existence and number of k-kings, the Path Partition Conjecture and pancyclicity. A brief section is devoted to homomorphisms in transitive digraphs.

Structural parameters for undirected graphs such as the path-width or tree-width of graphs have played a crucial role in developing a structure theory for graphs based on the minor relation and they have also found many algorithmic applications. Starting in the late 1990s, several ideas for generalizing this theory to digraphs have appeared. Broadly, for the purpose of this chapter, we distinguish these approaches into three categories: tree-width inspired, rank-width inspired and density based. The tree-width inspired approaches are based on the idea of generalizing the concept of undirected tree-width (or path-width) to digraphs. The various attempts, which we will discuss below, all have the goal of generalizing some natural property or some natural characterization of tree-width of undirected graphs to digraphs. In the same way as tree-width can be seen as a global connectivity measure for undirected graphs, the various versions of a directed analogue of tree-width measure global connectivity in digraphs. However, on digraphs, connectivity can be measured in many different natural ways. It turns out that equivalent characterizations of tree-width on undirected graphs yield different concepts on digraphs, with different properties, advantages and disadvantages.

This chapter is a survey of the four standard associative digraph products, namely the Cartesian, strong, direct and lexicographic products. Topics include metric properties, connectedness, hamiltonian properties and invariants. Special attention is given to issues of cancellation and unique prime factorization.

Obviously, there are countless digraph classes, so that any attempt to give a complete overview is doomed to failure. One has to restrict oneself to a selection. This chapter tries to survey some of the digraph classes that were not granted their own chapter in this book. As tournaments are arguably the best studied class of digraphs with a rich library of strong results, it is no wonder that they and their many generalizations are featured prominently throughout the book. In this regard, this chapter poses no exception. We examine arc-locally semicomplete digraphs, which generalize both semicomplete and semicomplete bipartite digraphs, as well as their generalizations \(\mathcal {H}_1\)-free digraphs and \(\mathcal {H}_2\)-free digraphs. The related classes of \(\mathcal {H}_3\)-free digraphs and \(\mathcal {H}_4\)-free digraphs are also briefly considered. Of course, there are also digraph classes (fairly) unrelated to tournaments such as kernel-perfect digraphs which are mentioned in several results throughout the book and appear in this chapter in a section mainly dedicated to perfect digraphs, game-perfect digraphs and weakly game-perfect digraphs. Furthermore, we consider some digraph classes that appear naturally in applications to other fields such as mathematical logic or computer science. Two such classes with applications in the construction of interconnection networks are de Bruijn digraphs and Kautz digraphs. Both classes can be defined using the line digraph operator. We also investigate line digraphs and iterated line digraphs in general. Minimal series-parallel digraphs, series-parallel digraphs and series-parallel partial order digraphs appear in flow diagrams and dependency charts and have an application to the problem of scheduling under constraints. We consider them briefly in a section on directed cographs, a generalization of series-parallel partial order digraphs.

Graph orientation, which provides a link between graphs and digraphs, is an actively studied area in the theory of graphs and digraphs. One of the fundamental problems asks whether a given graph admits an orientation that satisfies a prescribed property and to find such an orientation if it exists. In this chapter, we demonstrate a very simple orientation technique known as the lexicographic orientation method. We show how this method can be applied to obtain different types of orientations for various classes of graphs, and further extended to solve some orientation completion problems.