Counting edge crossings in a 2-layered drawing |
| |
Authors: | Hiroshi Nagamochi Nobuyasu Yamada |
| |
Affiliation: | Department of Information and Computer Sciences, Toyohashi University of Technology, Aichi 441-8580, Japan |
| |
Abstract: | Given a bipartite graph G=(V,W,E) with a bipartition {V,W} of a vertex set and an edge set E, a 2-layered drawing of G in the plane means that the vertices of V and W are respectively drawn as distinct points on two parallel lines and the edges as straight line segments. We consider the problem of counting the number of edge crossings. In this paper, we design two algorithms to this problem based on the dynamic programming and divide-and-conquer approaches. These algorithms run in O(n1n2) time and O(m) space and in O(min{n1n2,|E|log(min{|V|,|W|})}) time and O(m) space, respectively. Our algorithms outperform the previously fastest Θ(|E|log(min{|V|,|W|})) time algorithm for dense graphs. |
| |
Keywords: | Graph algorithms Edge crossings Bipartite graphs Counting Graph drawing Dynamic programming Divide-and-conquer |
本文献已被 ScienceDirect 等数据库收录! |
|