Thickness and outerthickness for embedded graphs

DOI10.1016/J.DISC.2018.02.024zbMATH Open1384.05075arXiv1512.04995OpenAlexW2964316365WikidataQ130049252 ScholiaQ130049252MaRDI QIDQ1744754FDOQ1744754

Authors: Xiaoya Zha, Baogang Xu 

Publication date: 19 April 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We consider the thickness $heta(G))$ and outerthickness $het{a}_o(G)$ of a graph G in terms of its orientable and nonorientable genus. Dean and Hutchinson provided upper bounds for thickness of graphs in terms of their orientable genus. More recently, Concalves proved that the outerthickness of any planar graph is at most 2. In this paper, we apply the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness of graphs. We first obtain better upper bounds for thickness. We then use a similar approach to provide upper bounds for outerthickness of graphs in terms of their orientable and nonorientable genera. Finally we show that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. We also show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5.

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

Recommendations

• Remarks on the thickness and outerthickness of a graph
• The thickness of graphs: A survey
• Thickness and Antithickness of Graphs
• Thickness and connectivity in graphs
• Geometric Thickness of Complete Graphs
• On the thickness of graphs of given degree
• scientific article; zbMATH DE number 4077286
• Remarks on the thickness of a graph
• On graph thickness, geometric thickness, and separator theorems
• The geometric thickness of low degree graphs

zbMATH Keywords

surfacedecompositionouterplanar graphplanar graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graphs on surfaces
• Decomposition of Finite Graphs Into Forests
• Surfaces, tree-width, clique-minors, and partitions
• Edge partition of planar sraphs into two outerplanar graphs
• The thickness of graphs: A survey
• Title not available (Why is that?)
• Outerplanar partitions of planar graphs
• Graphs with forbidden subgraphs
• On the genus and thickness of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Determining the thickness of graphs is NP-hard
• THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
• Title not available (Why is that?)
• Title not available (Why is that?)
• Die dicke des n-dimensionalen Würfel-graphen
• The thickness of a minor-excluded class of graphs

Cited In (16)

• Thickness‐two graphs part one: New nine‐critical graphs, permuted layer graphs, and Catlin's graphs
• Thickness and Antithickness of Graphs
• Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs
• On the genus and thickness of graphs
• Fold thickness of some classes of graphs
• Embedding graphs in cylinder and torus books
• Edge partition of graphs embeddable in the projective plane and the Klein bottle
• Thickness of the subgroup intersection graph of a finite group
• Title not available (Why is that?)
• Atomic Embeddability, Clustered Planarity, and Thickenability
• Face-width of embedded graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the bar visibility number of complete bipartite graphs
• Partial-dual Euler-genus distributions for bouquets with small Euler genus
• Thickness and connectivity in graphs

This page was built for publication: Thickness and outerthickness for embedded graphs

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