Linear-time algorithms for problems on planar graphs with fixed disk dimension

DOI10.1016/j.ipl.2006.08.006zbMath1185.68844OpenAlexW2002789839MaRDI QIDQ845887

Faisal N. Abu-Khzam, Michael A. Langston

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.08.006

zbMATH Keywords

planar graphsdesign of algorithmsouterplanar graphspathwidthapproximation algorithmsdisk dimension

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Approximating the pathwidth of outerplanar graphs
• Nonconstructive advances in polynomial-time complexity
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
• Approximation of pathwidth of outerplanar graphs
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Nonconstructive tools for proving polynomial-time decidability
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Linear-time algorithms for problems on planar graphs with fixed disk dimension