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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Exact and Approximate k-planarity Testing for Maximal Graphs of Small Pathwidth

  • Miriam Münch,
  • Maximilian Pfister,
  • Ignaz Rutter

摘要

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.