combinatoricsdiscrete mathematicseulerian-pathgraph theoryplanar-graphs
Given an adjacency matrix of a graph $G$, I was asked to do the following without drawing the graph:
A) Find the vertex of largest degree.
B) Does the graph have an Euler Circuit?
C) Is the graph Planar?
I did A and B. How can one justify if the graph is planar from adjacency matrix?
The dual of a planar graph depends on how it is embedded in the plane: "The same planar graph can have non-isomorphic dual graphs." (See Wikipedia illustration.)
Although this graph is not regular, it can be modified to obtain a cubic (3-regular) graph with more than one planar embedding and associated nonisomorphic dual graphs. Replace the left- and right-hand vertices of degree two in the top diagram with a "diamond" subgraph, connecting to its top and bottom nodes to produce all nodes of degree 3:
Now the outer face of the top graph will have its maximum degree 10, but the corresponding replacement in the alternative embedding yields a maximum degree 7 (shared by the outer face and one inner face). So the dual (multi-)graph depends on the embedding and cannot be inferred only from the adjacency matrix of the original graph.
So I'd say in the general sense you've asked, it cannot be done without pencil-and-paper or some other visualization of the embedding.
It is a directed graph, i.e. \begin{equation} \begin{matrix} a & & b\\ \updownarrow & X & \uparrow\\ c &\leftrightarrow & d \end{matrix} \end{equation}
where I used $X$ to denote a double-sided link between $a$-$d$ and $c$-$d$.
The direction of the edges is convention defined and could be reversed.
Best Answer
There are some simple conditions which, if transgressed, would mean that the graph is non-planar but in general there is nothing which could easily determine whether the graph is planar.
Since you said 'without drawing the graph' can we assume that the matrix is fairly small?
For a small number of vertices (e.g. $6$) it is easy to check whether or not the graph contains $K_{3,3}$ or a subgraph homeomorphic to $K_5$.
The reference you have already been given
https://en.wikipedia.org/wiki/Planar_graph
should be useful for the simple conditions.