Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2.
2019
Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class
$${{\mathcal {H}}}$$
. There are both polynomial-time solvable and NP-complete results in this direction, depending on $${{\mathcal {H}}}$$
. We present a general framework for the problem if $$\mathcal{H}$$
is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where $${{\mathcal {H}}}$$
is the class of outerplanar graphs and $${{\mathcal {H}}}$$
is the class of graphs of pathwidth at most 2.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
35
References
2
Citations
NaN
KQI