Exact and Approximate k-planarity Testing for Maximal Graphs of Small Pathwidth
摘要
A graph is k-planar, if it admits a drawing with at most k crossings per edge. Testing whether a given graph is k-planar is known to be NP-complete. For \(k = 1\) the problem remains NP-complete even for graphs of bounded pathwidth [3]. In this paper we give linear-time algorithms for efficiently testing 1-planarity of w-paths, where a w-path is a maximal graph with pathwidth w. Closely related to the concept of k-planarity is the local crossing number of a graph G; i.e. the minimum number k such that G is k-planar. For general graphs of pathwidth 3 we give a 7-approximation for the local crossing number. Finally we employ a technique used by Biedl et al. to derive an O(w)-approximation of the local crossing number for maximal pathwidth-w graphs.