Decomposition of graphs on surfaces
For \(G= (V,E)\) an Eulerian graph imbedded on a triangulizable surface \(S\), \(\text{mincr}(G, D)\) denotes the minimum number of intersections of \(G\) and \(D'\) (counting multiplicities), where \(D'\) ranges over all closed curves freely homotopic to \(D\) and not intersecting \(V\). Also, \(\text{mincr}(C,D)\) denotes the minimum number of intersections of \(C'\) and \(D'\) (counting multiplicities), where \(C'\) and \(D'\) range over all closed curves freely homotopic to \(C\) and \(D\), respectively. The authors show that \(E\) can be decomposed into closed curves \(C_1,C_2,\dots,C_k\) such that \(\text{mincr}(G,D)= \sum^k_{i=1}\text{mincr}(C_i, D)\), for each closed curve \(D\) on \(S\). They also present two corollaries, one for bipartite graphs and one for homotopic circulations.
- Making curves minimally crossing by Reidemeister moves
- Drawing a disconnected graph on the torus (extended abstract)
- scientific article; zbMATH DE number 3865324 (Why is no real title available?)
- scientific article; zbMATH DE number 5016711 (Why is no real title available?)
- Lower bounds for electrical reduction on surfaces
- 2- and 3-factors of graphs on surfaces
- scientific article; zbMATH DE number 6746901 (Why is no real title available?)
- Drawing disconnected graphs on the Klein bottle
- Removal of subgraphs and perfect matchings in graphs on surfaces
- Decomposition of graphs on surfaces and a homotopic circulation theorem
- Chain-connected component decomposition of curves on surfaces
This page was built for publication: Decomposition of graphs on surfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1369657)
