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 (4)

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

This page was built for publication: A fast algorithm for the product structure of planar graphs