Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

Golovach, P.A.; Heggernes, P.; Kratsch, D.; Lima, P.T.; Paulusma, D.; Bodlaender, Hans L.; Woeginger, Gerhard J.

Abstract

Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem is NP-complete in general, and consequently substantial effort has been dedicated to deciding whether a given graph has a square root that belongs to a particular graph class. There are both polynomial-time solvable and NP-complete cases, depending on the graph class. We contribute with new results in this direction. Given an arbitrary input graph G, we give polynomial-time algorithms to decide whether G has an outerplanar square root, and whether G has a square root that is of pathwidth at most 2.

Citation

Golovach, P., Heggernes, P., Kratsch, D., Lima, P., Paulusma, D., Bodlaender, H. L., & Woeginger, G. J. (2017). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. In Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers (275-288). https://doi.org/10.1007/978-3-319-68705-6_21

• Conference Name: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017)
• Conference Location: Eindhoven, The Netherlands
• Start Date: Jun 21, 2017
• End Date: Jun 23, 2017
• Acceptance Date: Jul 31, 2017
• Online Publication Date: Nov 2, 2017
• Publication Date: Jun 23, 2017
• Deposit Date: May 31, 2017
• Publicly Available Date: Nov 2, 2018
• Pages: 275-288
• Series Title: Lecture notes in computer science
• Series Number: 10520
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers.
• ISBN: 9783319687049
• DOI: https://doi.org/10.1007/978-3-319-68705-6_21