A fast algorithm for the product structure of planar graphs

DOI10.1007/s00453-020-00793-5OpenAlexW3118557737MaRDI QIDQ2663717

Pat Morin

Publication date: 19 April 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsqueue numberproduct structurenonrepetitive colouringadjacency labellingp-centered colouring

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items

Linear layouts of bipartite planar graphs, Improved Bounds for Centered Colorings, Fast decomposition algorithm based on two-dimensional wavelet transform for image processing of graphic design, Shorter Labeling Schemes for Planar Graphs

Cites Work

• A linear-time algorithm for a special case of disjoint set union
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Grad and classes with bounded expansion. I: Decompositions
• Algorithms for graphs embeddable with few crossings per edge
• Tree-depth, subgraph coloring and homomorphism bounds
• Graph Theory
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Implicat Representation of Graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Nonrepetitive colorings of graphs
• Planar graphs have bounded nonrepetitive chromatic number
• Planar Graphs Have Bounded Queue-Number
• Improved bounds for centered colorings