Pith. sign in

REVIEW 1 cited by

Computing bounded-width tree and branch decompositions of k-outerplanar graphs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1301.5896 v1 pith:6EOLTXPG submitted 2013-01-24 cs.DS cs.CC

Ioannis Katsikarelis This is my paper · ORCID
classification cs.DScs.CC
keywords k-outerplanarbranchdecompositiongraphgraphsprooftimetree
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

By a well known result the treewidth of k-outerplanar graphs is at most 3k-1. This paper gives, besides a rigorous proof of this fact, an algorithmic implementation of the proof, i.e. it is shown that, given a k-outerplanar graph G, a tree decomposition of G of width at most 3k-1 can be found in O(kn) time and space. Similarly, a branch decomposition of a k-outerplanar graph of width at most 2k+1 can be also obtained in O(kn) time, the algorithm for which is also analyzed.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs

    cs.DS 2025-06 conditional novelty 6.0 of 10

    H-TD computes a width-3 tree decomposition of any Halin graph in linear time, and its C++ prototype outperforms PACE 2017 solvers and libtw on Halin instances.

Pith tools