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

DOI10.1016/J.IPL.2006.08.006MaRDI QIDQ845887zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmspathwidthplanar graphsdesign of algorithmsouterplanar graphsdisk dimension

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1617251
• scientific article; zbMATH DE number 4066918
• Disk embeddings of planar graphs
• Approximate tree decompositions of planar graphs in linear time
• Approximate tree decompositions of planar graphs in linear time

Cites work

• scientific article; zbMATH DE number 1670677 (Why is no real title available?)
• scientific article; zbMATH DE number 4066918 (Why is no real title available?)
• scientific article; zbMATH DE number 3737730 (Why is no real title available?)
• scientific article; zbMATH DE number 795221 (Why is no real title available?)
• Approximating the pathwidth of outerplanar graphs
• Approximation of pathwidth of outerplanar graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Nonconstructive advances in polynomial-time complexity
• Nonconstructive tools for proving polynomial-time decidability
• On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
• On the Complexity of Covering Vertices by Faces in a Planar Graph

Cited in

(4)

• scientific article; zbMATH DE number 4066918 (Why is no real title available?)
• Light structures in infinite planar graphs without the strong isoperimetric property
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Approximation algorithms for NP-complete problems on planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845887)