Fomin, Fedor V.; Todinca, Ioan; Villanger, Yngve Exact algorithm for the maximum induced planar subgraph problem. (English) Zbl 1346.05283 Demetrescu, Camil (ed.) et al., Algorithms – ESA 2011. 19th annual European symposium, Saarbrücken, Germany, September 5–9, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23718-8/pbk). Lecture Notes in Computer Science 6942, 287-298 (2011). Summary: We prove that in an \(n\)-vertex graph, an induced planar subgraph of maximum size can be found in time \(O(1.7347^{n })\). This is the first algorithm breaking the trivial \(2^{n } n ^{O(1)}\) bound of the brute-force search algorithm for the Maximum Induced Planar Subgraph problem.For the entire collection see [Zbl 1222.68007]. Cited in 8 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity PDFBibTeX XMLCite \textit{F. V. Fomin} et al., Lect. Notes Comput. Sci. 6942, 287--298 (2011; Zbl 1346.05283) Full Text: DOI