Fundamental cycles and graph embeddings

DOI10.1007/S11425-009-0041-7zbMATH Open1185.05048arXiv0807.1652OpenAlexW2013070819MaRDI QIDQ1044271FDOQ1044271

Authors: Han Ren, HaoLing Li, Hong-Tao Zhao 

Publication date: 11 December 2009

Published in: Science in China. Series A (Search for Journal in Brave)

Abstract: In this paper we present a new Good Characterization of maximum genus of a graph which makes a common generalization of the works of Xuong, Liu, and Fu et al. Based on this, we find a new polynomially bounded algorithm to find the maximum genus of a graph.

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

Recommendations

• scientific article; zbMATH DE number 2147783
• Matchings, cycle bases, and the maximum genus of a graph
• Locally-maximal embeddings of graphs in orientable surfaces
• A relative maximum genus graph embedding and its local maximum genus
• The cycle's structure of embedded graphs in surfaces

zbMATH Keywords

spanning treesgraph embeddingsgenus of a graphfundamental cycles in graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graphs on surfaces
• Graph theory with applications
• How to determine the maximum genus of a graph
• Optimum matching forests I: Special weights
• Maximum genus of a graph in terms of its embedding properties.
• The maximum genus, matchings and the cycle space of a graph

Cited In (8)

• Odd components of co-trees and graph embeddings
• Survey on path and cycle embedding in some networks
• A new effective algorithm for the maximum genus of two types of 3-regular graphs
• Matchings, cycle bases, and the maximum genus of a graph
• New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces
• Clustering analysis of a dissimilarity: a review of algebraic and geometric representation
• An obstruction to embedding graphs in surfaces
• Separating and nonseparating disjoint homotopic cycles in graph embeddings

This page was built for publication: Fundamental cycles and graph embeddings

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