Worst case analysis of a greedy algorithm for graph thickness

DOI10.1016/S0020-0190(02)00432-5zbMath1173.68824OpenAlexW2089032661MaRDI QIDQ1007554

Koichi Yamazaki, Sinichiro Kawano

Publication date: 23 March 2009

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00432-5

zbMATH Keywords

greedy algorithmgraph algorithmsgraph thicknessmaximum planar subgraph

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

A simulated annealing algorithm for determining the thickness of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• The thickness of graphs: A survey
• Planarizing Graphs - A Survey and Annotated Bibliography
• Determining the thickness of graphs is NP-hard

This page was built for publication: Worst case analysis of a greedy algorithm for graph thickness