Welcome to MathOverflow

Question

2

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 implemented 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.

Is there any results about this question - NP-hardness or algortihm 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)?

Thanks for the answers

edited Jul 7 at 7:52

domotorp
4,068●7●25

asked Jun 22 at 11:00

David Herskovics
156●5

Joseph O'Rourke · Accepted Answer · 2012-07-07 18:53:57Z UTC

1

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.)

edited Jul 7 at 18:53

answered Jul 7 at 13:26

Joseph O'Rourke
43.1k●1●49●214

Thanks! This paper seems just what I looked for. – David Herskovics Jul 7 at 16:53

Graph implemened into the plane with segments as edges and we search for matching with no edges intersecting

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.