A 3-approximation for the pathwidth of Halin graphs

Fedor V. Fomin, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.

Original languageEnglish (US)
Pages (from-to)499-510
Number of pages12
JournalJournal of Discrete Algorithms
Issue number4
StatePublished - Dec 2006


  • Halin graph
  • Linear width
  • Pathwidth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'A 3-approximation for the pathwidth of Halin graphs'. Together they form a unique fingerprint.

Cite this