English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For every graph $H$, there exists a polynomial-time algorithm deciding if aplanar input graph $G$ can be contracted to~$H$. However, the degree of thepolynomial depends on the size of $H$. In this paper, we identify a class ofgraphs $\cal C$ such that for every $H \in \cal C$, there exists an algorithmdeciding in time $f(|V(H)|) \cdot |V(G)|^{\bigO{1}}$ whether a planar graph $G$can be contracted to~$H$. (The function $f(\cdot)$ does not depend on $G$.) Theclass $\cal C$ is the closure of planar triangulated graphs under taking ofcontractions. In fact, we prove that a graph $H \in \cal C$ if and only ifthere exists a constant $c_H$ such that if the tree-width of a graph is atleast $c_H$, it contains $H$ as a contraction. We also provide acharacterization of $\cal C$ in terms of minimal forbidden contractions.

Contracting planar graphs to contractions of triangulations