2
$\begingroup$

There are some points in the plane and some of them are connected with segments between them. We look at this structure as a graph immersed into the plane where the points are the vertices and the segments are the edges. We search for a maximum matching with no edges intersecting each other.

Are there any results about this question — NP-hardness or algorithm or characterisation even for some cases (the one case I see is when the graph is bipartite and the vertices of the two classes are on two parallel lines respectively)?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Perhaps the in-press 2012 paper, "Non-crossing matchings of points with geometric objects," by Aloupis et al. (Elsevier link; Prelim. PDF link) will help, either directly or through its references. (I have only passing familiarity with the contents of this paper myself.)
           Figure 1
(source: els-cdn.com)

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .