We introduce the face incidence matrix M (Γ) associated with a plane drawing Γ of a connected planar graph G. The diagonal entries count the faces whose boundaries contain a given vertex, while the off-diagonal entries count the faces whose boundaries contain a given edge. We prove that this matrix is independent of the chosen plane drawing and therefore defines a graph invariant M (G). An explicit formula is obtained: M (G) = D + 2A - B - diag (c (G - vᵢ) - 1), where A is the adjacency matrix, D is the degree matrix, B is the bridge matrix, and c (G - vᵢ) is the number of connected components after deleting the vertex vᵢ. We also establish a necessary and sufficient criterion for realizability of nonnegative integer matrices as face incidence matrices of connected planar graphs. Preprint. Submitted for journal consideration.
Vladimir Markov (Thu,) studied this question.