Back to search

McMaster University

Bi-incidence Matrices of Graphs for Spanning Trees and Cycle Spaces

Abstract

dc:description.abstract

This 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

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Zhao, Zicheng. Bi-incidence Matrices of Graphs for Spanning Trees and Cycle Spaces. 2026. https://hdl.handle.net/11375/33471