On the Treewidth and Pathwidth of Biconvex Bipartite Graphs

摘要

In this paper we explore the biclique structure of a biconvex bipartite graph G. We define two concatenation operators on bicliques of G. According to these operations, we show that G can be decomposed into two chain graphs G_L and G_R, and a bipartite permutation graph G_P. Using this representation, we propose linear-time algorithms for the treewidth and pathwidth problems on biconvex bipartite graphs.