Algorithms and obstructions for linear-width and related search parameters

Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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 (e1,...,er) in such a way that for every i=1,...,r-1, there are at most k vertices incident to edges that belong both to {e1,...,ei} and to {ei+1,...,er}. 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 languageEnglish (US)
Pages (from-to)239-271
Number of pages33
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Oct 15 2000


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

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Algorithms and obstructions for linear-width and related search parameters'. Together they form a unique fingerprint.

Cite this