Planar Drawing

This problem considers only finite, simple, undirected graphs that are connected. A planar graph is a graph that can be drawn in the plane so that no two edges cross, that is, edges meet only at shared end vertices. Such a drawing is a planar drawing of the graph. Figure 1 shows a planar graph and two of its planar drawings. Every planar graph is known to have a planar drawing in which all edges are straight line segments that do not intersect.

Figure 1. A planar graph and its planar drawings: (a) a complete graph with four vertices, (b) a planar drawing with curved edges, (c) a planar straight line drawing.

Testing whether a given graph is planar has been studied for a long time, and most known algorithms run in time linear in the number of vertices. A user of a planarity testing program sometimes wants more than a yes or no answer. Programmers make mistakes while implementing algorithms that were proven correct, and this is where certifying algorithms start.

When the user gives $X$ as an input and the program outputs $Y$, the user usually has no way of knowing whether $Y$ is a correct output on input $X$ or a value broken by a bug. A certifying algorithm produces, with each output, a certificate $Z$ that the particular output has not been compromised by a bug. By inspecting the certificate by hand or with a program, the user becomes convinced that the output is correct, or rejects the output as buggy. Checking $Z$ is automated with a checker, an algorithm that verifies that $Z$ proves $Y$ to be a correct output for $X$.

Consider the certificates a certifying algorithm for planarity testing should produce. If the input graph is planar, a planar drawing is the obvious certificate. If the graph is not planar, Kuratowski's theorem applies: a graph is planar if and only if it has no subgraph that is a subdivision of $K_5$ or of $K_{3,3}$. Here $K_5$ in Figure 2(a) is the complete graph with five vertices, and $K_{3,3}$ in Figure 2(b) is the complete bipartite graph with three vertices in each bipartition set. A subdivision of a graph is obtained by repeatedly subdividing edges with new vertices of degree 2, as in Figures 2(c) and 2(d). That is, a subdivision replaces the edges of the graph with paths between their end vertices so that no path has an inner vertex on another path or in the graph. So if a graph is not planar, a connected subgraph that is a subdivision of $K_5$ or of $K_{3,3}$ is a good certificate.

Figure 2. $K_5$, $K_{3,3}$, and their subdivisions: (a) $K_5$, (b) $K_{3,3}$, (c) a subdivision of $K_5$, (d) a subdivision of $K_{3,3}$.

Unlike checking whether a graph is a subdivision of $K_5$ or of $K_{3,3}$, checking whether a drawing is really planar is no easy task. So a combinatorial embedding, defined below, is adopted as the certificate for the affirmative case instead of a planar drawing. A straight line drawing in which no three vertices are collinear fixes, for each vertex $v$, the cyclic order of the vertices adjacent to $v$. Clockwise order is used here. The set of all these cyclic orders is a combinatorial embedding. Figure 3 shows a planar drawing and its corresponding combinatorial embedding. In the cyclic order $(2,3,4)$, for instance, the vertex after 2 is 3, the vertex after 3 is 4, and the vertex after 4 is 2.

Figure 3. A planar drawing and its combinatorial embedding: (a) a planar drawing, (b) its combinatorial embedding, (c) the four boundary cycles of the combinatorial embedding.

To check whether a combinatorial embedding is really planar, the notion of a boundary cycle is needed. Replace each undirected edge by two directed edges in opposite directions. The boundary cycle starting at a directed edge $(u, v)$ is defined as follows. If $u'$ is the vertex next to $u$ in the cyclic order for $v$, then $(v, u')$ is the next edge of the boundary cycle. Continue this way until the starting edge comes back. In the directed graph of Figure 3(c), starting at $(5,4)$, the cyclic order for vertex 4 is $(5,2,1,3)$ and the vertex next to 5 is 2, so the next edge is $(4,2)$. Continuing gives the boundary cycle $(5,4) \to (4,2) \to (2,3) \to (3,4) \to (4,5) \to (5,4)$.

A combinatorial embedding always partitions the set of directed edges into boundary cycles. Moreover, for a connected graph with $n > 1$ vertices and $m$ edges, a combinatorial embedding of the graph with $f$ boundary cycles is planar if and only if $n - m + f = 2$. Both facts have been proven. It therefore suffices to count the boundary cycles and check that equation.

Suppose an input graph $X$ is given, together with the output $Y$ and the certificate $Z$ of a certifying algorithm for planarity testing. Here $Y$ is a yes or no answer, and $Z$ is a combinatorial embedding or a subgraph of $X$ depending on the answer. A checker program splits into two modules. The first module tests whether the combinatorial embedding $Z$ is planar in the affirmative case, and whether the subgraph $Z$ is a subdivision of $K_5$ or of $K_{3,3}$ in the negative case. The second module tests whether $Z$ is a combinatorial embedding of $X$ or a subgraph of $X$, again depending on the answer. Write the first module. The vertices of the graph $X$ are indexed 1 to $n$.

The first line contains an integer indicating the output of a certifying algorithm, 1 in the affirmative case and -1 in the negative case. The second line contains $n$, the number of vertices of the graph $X$ ($2 \le n \le 5000$).

In the affirmative case, $n$ more lines describe the combinatorial embedding. Line $k$ contains $d_k$ followed by vertex numbers $x_1, x_2, \dots, x_{d_k}$, representing the cyclic order $(x_1, x_2, \dots, x_{d_k})$ of vertex $k$. These $n$ lines describe a combinatorial embedding of a connected simple graph on $n$ vertices: no number appears twice in one line, and $u$ appears in the list of $v$ exactly when $v$ appears in the list of $u$. The number of edges $m$ of this graph satisfies $1 \le m \le 50000$.

In the negative case, one line contains $n'$ and $m'$, the numbers of vertices and edges of the subgraph ($1 \le n' \le n$, $1 \le m' \le 50000$), and $m'$ lines follow, each containing two integers $u$ and $v$ that represent an edge between vertex $u$ and vertex $v$. Every vertex number lies in $\{1, \dots, n\}$. The certificate may be buggy: the same edge may be listed twice, an edge may join a vertex to itself, the graph may be disconnected, and the number of distinct vertices appearing in the list may differ from $n'$.

Print exactly one line.

In the affirmative case, print 1 if the given combinatorial embedding is planar, and -1 otherwise. That is, with $m$ the number of edges and $f$ the number of boundary cycles, print 1 if $n - m + f = 2$ and -1 otherwise.

In the negative case, print 1 if the given $m'$ edges form a subdivision of $K_5$ or of $K_{3,3}$, and -1 otherwise. The subgraph counts as such a subdivision only when all of the following hold. No edge is listed twice. No edge joins a vertex to itself. The number of distinct vertices in the edge list equals $n'$. The graph is connected. Every vertex has degree at least 2. Replacing each maximal path whose inner vertices all have degree 2 by a single edge yields exactly $K_5$ or exactly $K_{3,3}$. If that replacement produces a loop or two parallel edges, the subgraph is not a subdivision.