1369 . Planarity
Description
A graph is called planar if it can be drawn in the plane without any crossings. In a drawing of a graph, nodes are identified with points in the plane, and edges with lines connecting the corresponding end nodes. No edge is allowed to cross another edge or node in the drawing.
Recall that Kuratowski's theorem provides an easy test for determining planarity: A graph is planar if and only if it is not homeomorphic to any graph that contains the subgraph K3, 3 or the subgraph K5.
The figure on the left depicts K3, 3 and the one on the right K5:
The simplest graph homeomorphic to a given one can be obtained by repeating the following procedure while possible:
※Remove a vertex of degree 1 and its incident edge.
※Remove a vertex <b>v</b> of degree 2 and its two incident edges, and replace them by a new edge that joins the two nodes adjacent to <b>v</b>. For instance, <p>
would be reduced to
Note that if edge {u, w} was already in the graph, it would not be added again.
Write a program that determines whether a given undirected graph is planar or not.
Input Format
Input consists of zero or more test cases. Each test case consists of a graph.
A graph is given in the following way: First, a line contains two integers n and m, where n denotes the number of vertices of the graph, and m denotes its number of edges ( 1<=n<=20 and 0<=m). Then follow m lines, one for every edge of the graph, each containing two integers u and v (with u ≠ v) meaning that the graph contains the edge {u, v}. Vertices in the graph are labelled from 1 to n. There are not repeated edges.
Output Format
For each test case, print a line with the string YES if the graph is planar or with the string NO otherwise.
Sample Input 1
7 10 5 7 7 4 3 1 5 1 2 4 2 1 2 6 5 6 3 4 3 6 4 6 1 2 1 3 1 4 2 3 3 4 2 4 7 11 1 2 1 5 1 6 2 6 2 7 3 5 3 6 3 7 4 5 4 6 4 7
Sample Output 1
NO YES NO
Hints
Problem Source
Migrated from old NTUJ.
uva 10768
Subtasks
| No. | Testdata Range | Score |
|---|