Authors: Isolde Adler Mamadou Moustapha Kanté Ojoung Kwon
Publish Date: 2016/05/24
Volume: 78, Issue: 1, Pages: 342-377
Abstract
Linear rankwidth is a linearized variation of rankwidth and it is deeply related to matroid pathwidth In this paper we show that the linear rankwidth of every nvertex distancehereditary graph equivalently a graph of rankwidth at most 1 can be computed in time mathcal On2cdot log 2 n and a linear layout witnessing the linear rankwidth can be computed with the same time complexity As a corollary we show that the pathwidth of every nelement matroid of branchwidth at most 2 can be computed in time mathcal On2cdot log 2 n provided that the matroid is given by its binary representation To establish this result we present a characterization of the linear rankwidth of distancehereditary graphs in terms of their canonical split decompositions This characterization is similar to the known characterization of the pathwidth of forests given by Ellis Sudborough and Turner The vertex separation and search number of a graph Inf Comput 113150–79 1994 However different from forests it is nontrivial 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 vertexminors of the original graph for the right characterizationThe first author is supported by the German Research Council Project GalA AD 411/11 The third author is supported by Basic Science Research Program through the National Research Foundation of Korea NRF funded by the Ministry of Science ICT Future Planning 20110011653 A preliminary version appeared in the proceedings of WG’14
Keywords: