Bipartite permutation graphs have several nice characterizations in terms of vertex ordering. Besides, as AT-free graphs, they have a linear structure in the sense that any connected bipartite permutation graph has a dominating path. In the present paper, we elaborate the linear structure of bipartite permutation graphs by showing that any connected graph in the class can be stretched into a “path” with “edges” being chain graphs. A particular consequence from the obtained characterization is that the clique-width of bipartite permutation graphs is unbounded, which refines a recent result of Golumbic and Rotics for permutation graphs.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.