Fundamental cycles and graph embeddings

DOI10.1007/S11425-009-0041-7MaRDI QIDQ1044271zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

fundamental cycles in graphsgenus of a graphgraph embeddingsspanning trees

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)

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.

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

Cites work

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

Cited in

(11)

• Survey on path and cycle embedding in some networks
• An obstruction to embedding graphs in surfaces
• Orienting cycle elements in orientable rotation systems
• Odd components of co-trees and graph embeddings
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• 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
• Locally-maximal embeddings of graphs in orientable surfaces
• Simple greedy 2-approximation algorithm for the maximum genus of a graph
• Clustering analysis of a dissimilarity: a review of algebraic and geometric representation

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)