{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/33471"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/33471","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"Bi-incidence Matrices of Graphs for Spanning Trees and Cycle Spaces","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.","abstract_html":"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 <span class=\"etd-inline-math\">\\ker(B<sup>\\</sup>top)</span>. 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&#x27;s planarity criterion.","abstract_has_math":true,"creators":["Zhao, Zicheng"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computational Engineering and Science","school":null,"contributors":[],"advisors":["Mahyar, Hamidreza"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-18T19:36:41Z","subjects":[],"languages":[],"rights":["Attribution-NonCommercial-ShareAlike 4.0 International"],"rights_urls":["http://creativecommons.org/licenses/by-nc-sa/4.0/"],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/2255"],"render_values":[{"text":"https://doi.org/10.71548/2255","href":"https://doi.org/10.71548/2255","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/11375/33471","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/11375/33471","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F33471","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Mahyar, Hamidreza"]},{"key":"dc:contributor.department","label":"Department","values":["Computational Engineering and Science"]},{"key":"dc:creator","label":"Author","values":["Zhao, Zicheng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-08-19T20:01:48Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Attribution-NonCommercial-ShareAlike 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by-nc-sa/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/11375/33471","https://doi.org/10.71548/2255"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Applied Science (MASc)"]},{"key":"dc:title","label":"Title","values":["Bi-incidence Matrices of Graphs for Spanning Trees and Cycle Spaces"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Mahyar, Hamidreza"],"dc:contributor.department":["Computational Engineering and Science"],"dc:creator":["Zhao, Zicheng"],"dc:date.accessioned":["2026-08-19T20:01:48Z"],"dc:date.issued":["2026"],"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."],"dc:description.degree":["Master of Applied Science (MASc)"],"dc:identifier.uri":["https://hdl.handle.net/11375/33471","https://doi.org/10.71548/2255"],"dc:rights":["Attribution-NonCommercial-ShareAlike 4.0 International"],"dc:rights.uri":["http://creativecommons.org/licenses/by-nc-sa/4.0/"],"dc:title":["Bi-incidence Matrices of Graphs for Spanning Trees and Cycle Spaces"],"dc:type":["Thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:36:41Z"}