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.

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. (2017, June). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Presented at 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), Eindhoven, The Netherlands

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017)
• 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
• Print ISSN: 0302-9743
• 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
• Public URL: https://durham-repository.worktribe.com/output/1148413