MSOL restricted contractibility to planar graphs

DOI10.1007/978-3-642-33293-7_19MaRDI QIDQ4899253zbMATH OpenOpenAlexDBLPWikidataFDO

Authors James Abello, Pavel Klavík, Jan Kratochvíl, Tomáš Vyskočil

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.6070

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: We study the computational complexity of graph planarization via edge contraction. The problem CONTRACT asks whether there exists a set $S$ of at most $k$ edges that when contracted produces a planar graph. We work with a more general problem called $P$-RESTRICTEDCONTRACT in which $S$, in addition, is required to satisfy a fixed MSOL formula $P(S,G)$. We give an FPT algorithm in time $O(n^{2}f(k))$ which solves $P$-RESTRICTEDCONTRACT, where $P(S,G)$ is (i) inclusion-closed and (ii) inert contraction-closed (where inert edges are the edges non-incident to any inclusion minimal solution $S$). As a specific example, we can solve the $ell$-subgraph contractibility problem in which the edges of a set $S$ are required to form disjoint connected subgraphs of size at most $ell$. This problem can be solved in time $O(n^2{f}^{\prime }(k,ell))$ using the general algorithm. We also show that for $ellge2$ the problem is NP-complete.

Recommendations

• MSOL restricted contractibility to planar graphs
• Obtaining planarity by contracting few edges
• Obtaining planarity by contracting few edges
• Contractions of Planar Graphs in Polynomial Time
• Contracting planar graphs to contractions of triangulations

Cited in

(4)

• Obtaining planarity by contracting few edges
• Obtaining planarity by contracting few edges
• Contraction checking in graphs on surfaces
• MSOL restricted contractibility to planar graphs

This page was built for publication: MSOL restricted contractibility to planar graphs

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