Adjacency Labelling for Planar Graphs (and Beyond)

DOI10.1145/3477542MaRDI QIDQ5056430zbMATH OpenFDO

Authors Vida Dujmović, L. Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, Pat Morin

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

adjacency labellingplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an $n$-vertex planar graph $G$ is assigned a $(1+o(1))lo{g}_{2}n$-bit label and the labels of two vertices $u$ and $v$ are sufficient to determine if $uv$ is an edge of $G$. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ vertices such that every $n$-vertex planar graph is an induced subgraph of $U_n$. These results generalize to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and $k$-planar graphs.

Recommendations

• On \((p,1)\)-total labelling of planar graphs
• The \(L(2,1)\)-labeling on planar graphs
• Shorter Labeling Schemes for Planar Graphs
• Shorter Labeling Schemes for Planar Graphs
• Adjacency labeling schemes and induced-universal graphs
• Adjacency labeling schemes and induced-universal graphs
• Labelings of two classes of plane graphs
• Labeling of planar graphs with a condition on distance two
• Labeling Planar Graphs with Conditions on Girth and Distance Two
• Labelling of some planar graphs with a condition at distance two

Cited in

(45)

• Local certification of graphs with bounded genus
• An improved planar graph product structure theorem
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Adjacency labeling schemes and induced-universal graphs
• scientific article; zbMATH DE number 6712567 (Why is no real title available?)
• On minimizing the number of label transitions around a vertex of a planar graph
• Minimizing the number of label transitions around a nonseparating vertex of a planar graph
• Near optimal adjacency labeling schemes for power-law graphs
• Adjacency labeling schemes and induced-universal graphs
• Optimal induced universal graphs and adjacency labeling for trees
• Twin-width II: small classes
• Shorter Labeling Schemes for Planar Graphs
• Labeling schemes for bounded degree graphs
• Shorter Labeling Schemes for Planar Graphs
• Clustered 3-colouring graphs of bounded degree
• Representing graphs implicitly using almost optimal space
• Separating layered treewidth and row treewidth
• Improved product structure for graphs on surfaces
• Quasipolynomiality of the Smallest Missing Induced Subgraph
• The space complexity of sum labelling
• Sparse universal graphs for planarity
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• The product structure of squaregraphs
• Graph product structure for non-minor-closed classes
• Logical labeling schemes
• Optimal adjacency labels for subgraphs of Cartesian products
• Product structure of graph classes with bounded treewidth
• Small but unwieldy: a lower bound on adjacency labels for small classes
• Universal geometric graphs
• Product structure of graph classes with bounded treewidth
• Product structure of graphs with an excluded minor
• Graph product structure for \(h\)-framed graphs
• The r-dynamic chromatic number is bounded in the strong 2-coloring number
• Universal families of arcs and curves on surfaces
• Randomized communication and implicit graph representations
• Intersection graphs with and without product structure
• Product structure of graph classes with strongly sublinear separators
• Grid minors and products
• Treewidth 2 in the planar graph product structure theorem
• Structural properties of graph products
• Powers of planar graphs, product structure, and blocking partitions (extended abstract)
• Powers of planar graphs, product structure, and blocking partitions
• \(\mathcal{H}\)-clique-width and a hereditary analogue of product structure
• Subgraph-universal planar graphs for trees
• Isometric-universal graphs for trees

This page was built for publication: Adjacency Labelling for Planar Graphs (and Beyond)

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