Subgraphs of graphs on surfaces with high representativity

DOI10.1016/S0095-8956(03)00072-8zbMath1031.05040MaRDI QIDQ1417964

Katsuhiro Ota, Ken-ichi Kawarabayashi, Atsuhiro Nakamoto

Publication date: 6 January 2004

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

A theorem on paths in locally planar triangulations, Book embedding of locally planar graphs on orientable surfaces, 2-connected spanning subgraphs with low maximum degree in locally planar graphs, Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey, Dominating sets in triangulations on surfaces, Spanning closed walks and TSP in 3-connected planar graphs, Spanning trees: A survey, Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs, 3-trees with few vertices of degree 3 in circuit graphs, On certain spanning subgraphs of embeddings with applications to domination, Spanning trees in 3-connected K3,t-minor-free graphs, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. VII: Disjoint paths on a surface
• On 2-connected spanning subgraphs with low maximum degree
• Five-coloring maps on surfaces
• Trees in triangulations
• 4-connected projective planar graphs are Hamiltonian
• Spanning trees in locally planar triangulations
• 2-connected spanning subgraphs of planar 3-connected graphs
• 2-walks in circuit graphs
• Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
• Long cycles in graphs on a fixed surface
• Spanning planar subgraphs of graphs in the torus and Klein bottle
• A local property of polyhedral maps on compact two-dimensional manifolds
• Disjoint paths, planarizing cycles, and spanning walks
• A Theorem on Planar Graphs
• Connected subgraphs with small degree sums in 3-connected planar graphs
• Light paths in 4-connected graphs in the plane and other surfaces
• 2-connected 7-coverings of 3-connected graphs on surfaces
• Computing the orientable genus of projective graphs
• 2‐connected coverings of bounded degree in 3‐connected graphs
• Trees in Polyhedral Graphs