Improved product structure for graphs on surfaces

DOI10.46298/dmtcs.8877zbMath1516.05145arXiv2112.10025MaRDI QIDQ6045446

Tony Huynh, Unnamed Author, Robert Hickingbotham, David R. Wood

Publication date: 31 May 2023

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graphs on surfacesproduct structure

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Shallow Minors, Graph Products, and Beyond-Planar Graphs, The product structure of squaregraphs, Graph product structure for non-minor-closed classes

Cites Work

• Unnamed Item
• Characterizing and recognizing 4-map graphs
• An annotated bibliography on 1-planarity
• Layered separators in minor-closed graph classes with applications
• Recognizing hole-free 4-map graphs in cubic time
• Adjacency Labelling for Planar Graphs (and Beyond)
• Planar graphs have bounded nonrepetitive chromatic number
• Planar Graphs Have Bounded Queue-Number
• Shorter Labeling Schemes for Planar Graphs
• Improved Bounds for Centered Colorings
• Structure of Graphs with Locally Restricted Crossings
• Clustered 3-colouring graphs of bounded degree
• Book embeddings of nonplanar graphs with small faces in few pages