## Abstract

The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering (e_{1},...,e_{r}) in such a way that for every i=1,...,r-1, there are at most k vertices incident to edges that belong both to {e_{1},...,e_{i}} and to {e_{i+1},...,e_{r}}. In this paper, we give a set of 57 graphs and prove that it is the set of the minimal forbidden minors for the class of graphs with linear-width at most two. Our proof also gives a linear time algorithm that either reports that a given graph has linear-width more than two or outputs an edge ordering of minimum linear-width. We further prove a structural connection between linear-width and the mixed search number which enables us to determine, for any k≥1, the set of acyclic forbidden minors for the class of graphs with linear-width≤k. Moreover, due to this connection, our algorithm can be transfered to two linear time algorithms that check whether a graph has mixed search or edge search number at most two and, if so, construct the corresponding sequences of search moves.

Original language | English (US) |
---|---|

Pages (from-to) | 239-271 |

Number of pages | 33 |

Journal | Discrete Applied Mathematics |

Volume | 105 |

Issue number | 1-3 |

DOIs | |

State | Published - Oct 15 2000 |

## Keywords

- Graph algorithm
- Graph minor
- Graph searching
- Linear width
- Obstruction set

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics