Let c denote a non-negative constant. Suppose that we are given an edge-weighted bipartite graph G=(V,E) with its 2-layered drawing and a family X of intersecting edge pairs. We consider the problem of finding a maximum weighted matching M* such that each edge in M* intersects with at most c other edges in M*, and that all edge crossings in M* are contained in X. In the present paper, we propose polynomial-time algorithms for the problem for c=1 and 2. The time complexities of the algorithms are O((k+m)log n) for c=1 and O(m^4log n+k^3+n(k^2+log n)) for c=2, respectively, where n=|V|, m=|E| and k=|X|.
@cite_10 studied the problem of finding a subgraph that has few edge crossings; given a graph (not necessarily bipartite) and its geometric drawing (i.e., every vertex is specified by a 2D point, all edges are drawn as straight line segments, and no two edges overlap or intersect at a vertex), we are asked to find a subgraph of a certain class that makes the minimum number of edge crossings. They showed that, for spanning trees, @math - @math paths, cycles, matchings of a fixed size, and 1- or 2-factors, it is NP-hard to approximate the minimum number of edge crossings within a factor of @math for any @math , where @math denotes the number of edge crossings in the given graph. They also presented fixed-parameter algorithms to decide whether there is a non-crossing subgraph of one of the above graph classes, where @math is used as the parameter.
@cite_10
2161036821
A problem arising in the design of vacuum systems and having applications to some natural problems of interconnection design is described as follows. (1) Given a set X and subsets @math of @math , satisfying @math , find a graph G with vertex set X and the minimum number of edges such that for any i, the subgraph induced by @math has a connected component containing @math .Two other problems related to this one are the following ones. (2) Given a set X and subsets @math such that @math , find a graph G with vertex set X and the minimum number of edges such that for any i the subgraph @math induced by @math in G is connected. (3) Given a set X and subsets @math such that @math , find a graph G with vertex set X, find a graph G with vertex set X and the minimum number of edges such that for any subset I of @math , the subgraph induced by @math is co...