2014/03/05 by Isolde Adler, Adler, Isolde, Mamadou Moustapha Kanté +4 · 1 citation
Computer Science · Mathematics · #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems #acm:05C85 #cs.DM #cs.DS #math.CO #msc:05C85
paper · pdf · doi:10.48550/arxiv.1403.1081
28 pages, 3 figures, 2 table. A preliminary version appeared in the proceedings of WG'14
openalex publication_date 2014/03/05 · arxiv created 2015/08/21 · arxiv updated 2015/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every n-vertex distance-hereditary graph, equivalently a graph of rank-width at most 1, can be computed in time O(n2⋅ log2 n), and a linear layout witnessing the linear rank-width can be computed with the same time complexity. As a corollary, we show that the path-width of every n-element matroid of branch-width at most 2 can be computed in time O(n2⋅ log2 n), provided that the matroid is given by an independent set oracle. To establish this result, we present a characterization of the linear rank-width of distance-hereditary graphs in terms of their canonical split decompositions. This characterization is similar to the known characterization of the path-width of forests given by Ellis, Sudborough, and Turner [The vertex separation and search number of a graph. Inf. Comput., 113(1):50--79, 1994]. However, different from forests, it is non-trivial to relate substructures of the canonical split decomposition of a graph with some substructures of the given graph. We introduce a notion of `limbs' of canonical split decompositions, which correspond to certain vertex-minors of the original graph, for the right characterization.