Consider adjacency matrix of $8$ vertex bipartite graph with $4$ vertices of each color:
\begin{bmatrix}
0& 1& 1& 0\\
1& 0& 1& 1\\
1& 1& 0& 1\\
1& 1& 1& 0
\end{bmatrix}
Is the corresponding bipartite matrix planar?
Given an $n\times n$ matrix, how do you find if underlying bipartite matrix is planar?
Also is there a test if the matrix under consideration is general adjacency matrix?
Best Answer
The first complete characterization of which (undirected, simple) graphs can be embedded in the plane (without edge crossings) was given by Kuratowski in 1930 (K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math., 15:271–283):
However it wasn't until 1974 that a linear time algorithm to decide planarity was described by Hopcroft and Tarjan through cycle-based path addition. A succession of improvements (Gries and Xue, 1988) followed (our sketch below is adapted from their account).
Currently a number of linear time algorithms are known for producing a planar embedding (or determining that none is possible) for a graph. A good survey is the extensive book chapter "Planarity Testing and Embedding" by Maurizio Patrignani (Handbook of Graph Drawing and Visualization, 2013).
Sketch of cycle-based path-addition
It is obvious that a graph $G$ is planar if and only if each connected component is. Less obvious is the fact (Lemma 2.1, Gries and Xue) that $G$ is planar if and only if each of its biconnected components is planar. [Two nodes are biconnected iff there is a cycle containing both, and this is an equivalence relation on vertices. The biconnected components combine as an acyclic forest graph, which is easily embedded in the plane.] So it suffices to give an algorithm for biconnected $G$.
If $G$ is biconnected (and has more than one vertex), then it contains a simple cycle $C$. By the Jordan Curve Theorem, such a cycle $C$ when embedded into the plane will separate it into one bounded and one unbounded region. So the first step is to choose a cycle, and then we work out what goes "inside" and what goes "outside" the embedding of $C$.
Since $G$ is biconnected, the edges of $G$ not in $C$ can be partitioned into a set $S$ of segments such that two of these edges are in the same segment iff there exists a path from an endpoint of one edge to an endpoint of the other edge that otherwise avoids any vertex in $C$. As $G$ is biconnected, at least two vertices of any segment $s\in S$ will be on $C$, and we call such vertices the attachments of $s$ to $C$.
A segment is connected, so if $G$ gets embedded in the plane, each segment in $S$ will fall exclusively inside or outside the embedding of $C$. While we can switch the inside and outside regions (thus arrange any one segment in either the inside or outside region), the following conditions tell us when a pair of distinct segments $s_1,s_2 \in S$ conflict and must be put into opposite regions:
However if all the segments can be assigned to disjoint subsets, $S = S_1 \cup S_2$, so that within each subset there are no such conflicts, then $G$ is planar if and only if each segment in $S$ is planar. The algorithm can thus proceed recursively to determine planarity of $G$ in linear time (TO DO: note at end for a bit more detail on this).
The Example Asked in This Question is Planar
The bipartite graph at issue here is indeed planar, as may be seen from the following embedding. Let $a,b,c,d$ be the vertices of one part, corresponding to the rows of the given biadjacency matrix, and let $\alpha, \beta, \gamma, \delta$ be the vertices of the other part, corresponding to its columns:
$$ \begin{bmatrix} 0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0 \end{bmatrix} $$
By depth-first search we find this graph to be one biconnected component. There is an $8$-cycle $C$ reaching all eight vertices:
$$ \underbrace{\alpha \to c \to \delta \to b \to \gamma \to a \to \beta \to d \to \alpha}_{\text{8-cycle } C} $$
Once this $C$ is drawn, it accounts for eight of the $11$ edges, and the remaining three edges ($\alpha - b$, $\beta - c$, $\gamma - d$) are easily drawn on one side or the other of the embedding of $C$:
This diagram suggests that all our edges may be drawn in the plane as non-crossing straight line segments. That such is always the case is a perhaps surprising fact about (simple, loopless) planar graphs called Fáry's theorem.
$\mathbf{K}_5$ and $\mathbf{K}_{3,3}$ are Not Planar
The power of the algorithm to dispose of non-planar graphs can be illustrated by the "forbidden subgraphs" of Kuratowski's characterization.
$K_5$, the complete graph on five vertices, is biconnected with a $5$-cycle:
$$ a \to b \to c \to d \to e \to a $$
Apart from this $5$-cycle the graph has $\binom{5}{2} - 5 = 5$ additional edges, each of which forms a separate segment with endpoints on the cycle:
$$ a-c\;,\;b-d\;,\;c-e\;,\;a-d\;,\;b-e $$
If we are to split these five into two subsets free of conflicts, one of them must hold at least three segments. By symmetry we are free to pick one of the edges, say $a-c$. Then this edge conflicts with $b-d$ and $b-e$, so we would have to use $a-d$ and $c-e$ to get the needed three segments. However $a-d$ and $c-e$ conflict, so there's no way to partition the segments into inside/outside regions. Therefore $K_5$ is not a planar graph.
$K_{3,3}$, the complete bipartite graph on two parts of three nodes apiece, is biconnected with a $6$-cycle:
$$ \alpha \to a \to \beta \to b \to \gamma \to c \to \alpha $$
Apart from this $6$-cycle the graph has $(3\cdot 3) - 6 = 3$ additional edges, each of which forms a separate segment with endpoints on the cycle:
$$ \alpha - b\;,\;\beta - c\;,\;\gamma - a $$
Any two of these three segments conflict, so we cannot split them into two conflict-free subsets. The graph $K_{3,3}$ is therefore not planar.