查看文章

Planarity is an extensively studied topic within the graph theory domain. Planarity describes the potential for a graph to be embedded on a Euclidean plane without having any of its edges cross, and planarity is consequently a subject of particular interest in the context of graphs with nodes representing entities that are subject to physical constraints. While graph planarity has been extensively studied as a theoretical topic, it has also been successfully practically applied to architectural design [1] and circuit board design [2]. Our prior work found planarity to be a topic of interest in biological networks, specifically with regard to protein-protein interaction and domain-domain interaction networks. This work presents a novel parallel algorithm that produces planar approximations of large networks, which may be used to assess the relative planarity of large networks, for further analyses or ensemble methods, and …