McMaster University
Bi-incidence Matrices of Graphs for Spanning Trees and Cycle Spaces
Abstract
dc:description.abstractThis thesis studies a primal-dual bi-incidence matrix construction associated with spanning trees and cycle spaces. For a connected plane graph, let \(B\) be a reduced primal incidence matrix and let \(C\) be the reduced incidence matrix of the directed plane dual. Recent work proved that \(|\det([B\mid C])|=\tau(G)\), where \(\tau(G)\) is the number of spanning trees of \(G\). This identity determines the absolute value of the determinant, but does not describe the signs of the individual spanning-tree terms appearing in a determinant expansion. Specifically, this proof did not explain why the signs are coherent among all spanning trees. Given this, through a self-contained proof, we prove that every tree carries the same global sign, so there is no cancellation. We first give a weighted refinement of this identity. After introducing diagonal edge-weight matrices, we prove that there is such a global sign that is independent of the spanning tree \(T\). The proof uses a block Laplace expansion, the incidence-minor characterization of spanning trees, tree-cotree duality, and a complementary-minor sign-coherence argument based on exterior products and Hodge duality. We then separate this determinant mechanism from planarity. For an arbitrary connected graph, the directed-dual block is replaced by a cycle-space complement \(Q\), whose columns form a basis of \ker(B\top). We prove the weighted basis-cobasis determinant identity in a similar form, which shows that sign coherence comes from the orthogonal cut-cycle decomposition of the edge space. Planarity is then interpreted as the existence of a sparse facial realization of this cycle-space complement, in connection with Mac Lane's planarity criterion.
Degree
thesis:*- Department dc:contributor.department
- Computational Engineering and Science
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Zhao, Zicheng
- Advisor dc:contributor.advisor
-
- Mahyar, Hamidreza
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-ShareAlike 4.0 International
- Licence dc:rights.uri
Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/2255