MENT
发表于 2025-3-30 10:13:51
http://reply.papertrans.cn/39/3880/387913/387913_51.png
Neonatal
发表于 2025-3-30 15:01:08
Turning Cliques into Paths to Achieve Planarityet is a path, in such a way that the resulting subgraph of . is planar. We study this problem when . is a simple topological graph, and establish its complexity in relation to .-planarity. We prove that . . is NP-complete even when . and . is a simple 3-plane graph, while it can be solved in linear time, for any ., when . is 1-plane.