New upper bounds on the decomposability of planar graphs
From MaRDI portal
Publication:3376690
DOI10.1002/jgt.20121zbMath1085.05049OpenAlexW4232845306WikidataQ56679466 ScholiaQ56679466MaRDI QIDQ3376690
Fedor V. Fomin, Dimitrios M. Thilikos
Publication date: 24 March 2006
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.20121
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings, Surprising Applications of Treewidth Bounds for Planar Graphs, On the minimum corridor connection problem and other generalized geometric problems, An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs, Fixed-Parameter Tractability of Treewidth and Pathwidth, Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms, New analysis and computational study for the planar connected dominating set problem, A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs, Unnamed Item, Transversals of longest cycles in partial k‐trees and chordal graphs, Upward book embeddability of \(st\)-graphs: complexity and algorithms, A Linear Kernel for Planar Feedback Vertex Set, Practical algorithms for branch-decompositions of planar graphs, Intersecting longest paths in chordal graphs, Enumerating Grid Layouts of Graphs, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, Subexponential parameterized algorithms, Computational study on a PTAS for planar dominating set problem, Computing branchwidth via efficient triangulations and blocks, Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms, Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs, The role of planarity in connectivity problems parameterized by treewidth, NP-completeness results for partitioning a graph into total dominating sets, Complexity of fall coloring for restricted graph classes, A Local Search Algorithm for Branchwidth, Upward Book Embeddings of st-Graphs, Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs, Computational study on planar dominating set problem
Cites Work
