DMPG '15 G2 - 1-String B2-VPG Representation of Planar Graphs

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are listening to an interesting lecture about 1-String B2-VPG Representation of Planar Graphs given by M. Derka, but as the presentation goes on and your understanding of the lecture lessens, your thoughts wander off into the realm of planar graphs…

You dream of a glorious planar graph. You wonder: what is the size of the maximum clique in this graph? A clique is a subgraph of the graph such that each pair of vertices in the clique are connected to each other by an edge. Specifically, a set of one single vertex is considered a clique. A maximum clique is a clique that has the most vertices out of all cliques in a graph.

Since you are skeptical that your graph is actually planar, you are determined to remove some edges such that it becomes planar. Therefore, your procedure of making the graph is as follows: first, you draw N points on the Cartesian plane. These will be your vertices, numbered from 1 to N. Then, you consider M straight-line edges between the points in order. If adding an edge would make the graph non-planar (i.e. it intersects a previously added edge somewhere which is not the endpoints of the edge), you discard it. In particular, two lines that have infinitely many common points do intersect. Otherwise, you add it to the graph.

After making your graph in this fashion, you are too exhausted to complete your original goal by hand. Therefore, you decide to redo the whole procedure, but this time with a program you are about to write.

Input Specification

The first line of input will have two integers N and M (0 \le M \le 5\,000).
The next N lines will have integer x and y pairs (0 \le x, y \le 10\,000), the coordinates of each vertex in the graph in order from vertex 1 to vertex N. No two points will be at the same location. Additionally, no three points will be collinear.
The next M lines will have u and v pairs (1 \le u, v \le N, u \neq v), indicating that you should consider adding an edge from u to v.


Subtask 1 [30%]

2 \le N \le 20

Subtask 2 [20%]

2 \le N \le 40

Subtask 3 [50%]

2 \le N \le 300

Output Specification

You should output the size of the maximum clique on one line.

Sample Input

4 6
0 0
0 1
1 1
1 0
1 2
2 3
3 4
4 1
1 3
2 4

Sample Output


Explanation of Output for Sample Input

The graph is a square, but the last edge 2 \leftrightarrow 4 isn't in the graph as its presence would make the given embedding of the graph non-planar. There are two maximum cliques of size 3, \{1, 2, 3\} and \{1, 3, 4\}.


  • 1
    sumeet_varma  commented on May 28, 2015, 2:24 p.m.

    *Is the subtask weight assigned correctly? I mean 50% for n <= 20 and just 30% for n <= 300 ?

    • 0
      FatalEagle  commented on May 28, 2015, 3:30 p.m. edit 2

      Fixed, thanks for noticing. I've updated the problem statement.

  • -20
    bossu  commented on May 28, 2015, 1:28 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

  • 1
    Egor  commented on May 28, 2015, 11:49 a.m.

    Does segments intersect if they has infinitely many common points?

    • 0
      FatalEagle  commented on May 28, 2015, 11:57 a.m. edit 2

      Sorry, consider that they DO intersect. I will verify the test data again.

      • 0
        Egor  commented on May 28, 2015, 12:00 p.m.

        Please reply when you'll finish this check

        • 2
          FatalEagle  commented on May 28, 2015, 12:20 p.m.

          I am really sorry. I will remove all cases with 3 collinear points. The reason is because that no matter which way of interpreting this scenario, the result is not good.

  • 0
    nullptr  commented on May 28, 2015, 11:36 a.m.

    Can we assume no three points are collinear?