Linear-Branch-Decomposition of Digraph

Takaaki Fujita 1,∗

1Independent Researcher, Shinjuku, Shinjuku-ku, Tokyo, Japan

Email: takaaki.fujita060@gmail.com

Abstract

The study of graph width parameters is a well-established field within graph theory. Recently, numerous

researchers have been actively extending undirected width parameters to directed graphs, resulting in a wide

range of studies on directed width parameters. In this paper, we introduce a new concept called Directed

Linear-Branch-Width, which extends the (Undirected) Linear-Branch-Width to digraphs. We also investigate

its relationship and hierarchy with Directed Path-width, Directed Cut-width, and Directed Neighbourhood-

width.

Keywords: Directed Tree-width; Directed Branch-width; Directed Graph; Branch-width; Linear-branch-

width