Bounded expansion and nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of uniformly sparse graphs which includes the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs. Since their initial definition it was shown that these graph classes can be defined in many equivalent ways: by generalised colouring numbers, neighbourhood complexity, sparse neighbourhood covers, a game known as the splitter game, and many more. We study the corresponding concepts for directed graphs. We show that the densities of bounded depth directed minors and bounded depth topological minors relate in a similar way as in the undirected case. We provide a characterisation of bounded expansion classes by a directed version of the generalised colouring numbers. As an application we show how to construct sparse directed neighbourhood covers and how to approximate directed distance-r dominating sets on classes of bounded expansion. On the other hand, we show that linear neighbourhood complexity does not characterise directed classes of bounded expansion.
展开▼
机译：Nesetril和Ossona de Mendez介绍的有界扩展和无处致密的图形类，形成了各种均匀稀疏图的均匀稀疏图，其中包括平面图的类，实际上是所有课程，其中包括被排除的未成年人，以及有界度图。由于它们的初始定义显示，这些图形类可以以许多等价方式定义：通过广义着色数字，邻域复杂性，稀疏的邻域盖，称为分配器游戏的游戏等等。我们研究了定向图表的相应概念。我们表明有界深度定向的未成年人和有界深度拓扑成本的密度以与无向壳体类似的方式相关。我们通过指向的广义着色数字来提供有界扩展类的表征。作为一个应用程序，我们展示了如何构建稀疏指向的邻居封面以及如何在有界扩展类上进行近似指示的距离-R主导集。另一方面，我们表明线性邻域复杂性没有表征有界扩展的定向类。
展开▼
