Thickness and outerthickness for embedded graphs
From MaRDI portal
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)
Abstract: We consider the thickness and outerthickness 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.
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
Cites work
- scientific article; zbMATH DE number 4208089 (Why is no real title available?)
- scientific article; zbMATH DE number 15359 (Why is no real title available?)
- scientific article; zbMATH DE number 867695 (Why is no real title available?)
- scientific article; zbMATH DE number 3195968 (Why is no real title available?)
- scientific article; zbMATH DE number 3199421 (Why is no real title available?)
- Decomposition of Finite Graphs Into Forests
- Determining the thickness of graphs is NP-hard
- Die dicke des n-dimensionalen Würfel-graphen
- Edge partition of planar sraphs into two outerplanar graphs
- Graphs on surfaces
- Graphs with forbidden subgraphs
- On the genus and thickness of graphs
- Outerplanar partitions of planar graphs
- Surfaces, tree-width, clique-minors, and partitions
- THE THICKNESS OF AN ARBITRARY COMPLETE GRAPH
- The thickness of a minor-excluded class of graphs
- The thickness of graphs: A survey
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
- Embedding graphs in cylinder and torus books
- Fold thickness of some classes of graphs
- Edge partition of graphs embeddable in the projective plane and the Klein bottle
- scientific article; zbMATH DE number 15359 (Why is no real title available?)
- Thickness of the subgroup intersection graph of a finite group
- Atomic Embeddability, Clustered Planarity, and Thickenability
- Face-width of embedded graphs
- scientific article; zbMATH DE number 734462 (Why is no real title available?)
- scientific article; zbMATH DE number 4077286 (Why is no real title available?)
- 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)
