0

I have this task: Given n vertices, that are connected each to the next and previous, forming a railway like: 1--2--3--4...

Given a set of edges in the form of i -> j, and the edge can go either north of the railway, or south, the question is whether you can build the given edges (each either north or south of the railway) so that no two edges intersect?

My idea was with backtracking checking each of the given pairs first going north, and then going south combined with a matrix A where I keep if the edge from i to j (A[i][j]) is build north or south, and determine if I can build the next one so that it is not intersecting the precious ones, but it was too slow. Is there an existing algorithm that does what I want or can you help me with it?

Kedar Mhaswade
  • 4,535
  • 2
  • 25
  • 34
Poyr23
  • 123
  • 1
  • 9

1 Answers1

0

First, we can assume without loss of generality all the routes i->j are from lower to higher numbers -- otherwise we can simply reverse any routes from higher to lower numbers.

Now, consider the graph where vertices are routes i->j in your railway, and edges exist between i->j and i'->j' if neither i <= i' < j' <= j or i' <= i < j <= j' (that is, the routes i->j and i'->j' have an edge between them in the graph if they would cross if they were on the same side of the train tracks).

The railway can be constructed if and only if this graph is bipartite. To test that efficiently, one can use an algorithm described for example here: How to find if a graph is bipartite?

Community
  • 1
  • 1
Paul Hankin
  • 54,811
  • 11
  • 92
  • 118