Determining the Smallest k Such That G Is k-Outerplanar

DOI10.1007/978-3-540-75520-3_33zbMath1151.05331OpenAlexW1577244476MaRDI QIDQ3527226

Frank Kammer

Publication date: 25 September 2008

Published in: Algorithms – ESA 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-75520-3_33

zbMATH Keywords

NP-hardfixed-parameter algorithmsouterplanarity index\(k\)-outerplanarSPQR trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

Efficient reassembling of three-regular planar graphs ⋮ Topological morphing of planar graphs ⋮ Rings whose cozero-divisor graph has crosscap number at most two ⋮ Nilpotent graphs with crosscap at most two ⋮ Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time ⋮ Approximating the minimum hub cover problem on planar graphs ⋮ Approximation Algorithms for Facial Cycles in Planar Embeddings

This page was built for publication: Determining the Smallest k Such That G Is k-Outerplanar