We study relations between geometric embeddings of graphs and the spectrum of associated matrices, focusing on outerplanar embeddings of graphs. For a simple connected graph G = (V, E), we define a "good” G-matrix as a V × V matrix with negative entries corresponding to adjacent nodes, zero entries corresponding to distinct nonadjacent nodes, and exactly one negative eigenvalue. We give an algorithmic proof of the fact that if G is a 2-connected graph, then either the nullspace representation defined by any "good” G-matrix with corank 2 is an outerplanar embedding of G, or else there exists a "good” G-matrix with corank 3.
Additional Metadata
Editor M. Loebl (Martin) , J. Nešetřil (Jaroslav) , R. Thomas (Robin)
Persistent URL dx.doi.org/10.1007/978-3-319-44479-6_23
Citation
Lovász, L, & Schrijver, A. (2017). Nullspace embeddings for outerplanar graphs. In M Loebl, J Nešetřil, & R Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute to Jiri Matousek (pp. 571–591). doi:10.1007/978-3-319-44479-6_23