Treewidth of Circular-Arc Graphs

DOI10.1137/S0895480191193789zbMath0814.05065OpenAlexW2027388354MaRDI QIDQ4317710

C. Pandu Rangan, Karan Sher Singh, Ravi Sundaram

Publication date: 20 December 1994

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480191193789

zbMATH Keywords

intersection graphtreewidthtree-decompositioncircular-arc graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Treewidth for graphs with small chordality ⋮ Chordal embeddings of planar graphs ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs ⋮ On the Maximum Weight Minimal Separator ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ How to use the minimal separators of a graph for its chordal triangulation ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Listing all potential maximal cliques of a graph

This page was built for publication: Treewidth of Circular-Arc Graphs