Nullspace embeddings for outerplanar graphs

DOI10.1007/978-3-319-44479-6_23MaRDI QIDQ4604390zbMATH OpenOpenAlexFDO

Authors László Lovász, Alexander Schrijver

Publication date 26 February 2018

Published in A Journey Through Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.03434

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: 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 $VimesV$ 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 it $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.

Recommendations

• On the null space of a Colin de Verdière matrix
• Minimum rank of outerplanar graphs
• Maximum nullity of outerplanar graphs and the path cover number
• Embedding k-Outerplanar Graphs into l1
• In-trees and plane embeddings of outerplanar graphs

Cites work

• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• A short proof of the planarity characterization of Colin de Verdière
• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• On the null space of a Colin de Verdière matrix
• Positive semidefinite matrix completion, universal rigidity and the strong Arnold property
• Rigidity and energy
• Sachs' linkless embedding conjecture
• Steinitz representations of polyhedra and the Colin de Verdière number
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• The strong Arnold property for 4-connected flat graphs

Cited in

(3)

• On the null space of a Colin de Verdière matrix
• Embedding k-Outerplanar Graphs into l1
• Compatible forts and maximum nullity of a graph

This page was built for publication: Nullspace embeddings for outerplanar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604390)