Small universal graphs for bounded-degree planar graphs

DOI10.1007/S004930200017MaRDI QIDQ1872891zbMATH OpenOpenAlexFDO

Authors Michael Capalbo

Publication date 18 May 2003

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930200017

zbMATH Keywords

embeddingplanar graphsuniversal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

If \(N\), \(k\) are natural numbers, a graph on \(O_k(N)\) vertices is explicitly constructed that embeds every \(N\)-vertex planar graph with maximum degree \(\leq k\).

Cited in

(12)

• The maximum sum of degrees above a threshold in planar graphs
• On universal graphs for planar oriented graphs of a given girth
• Planar graphs with few vertices of small degree
• Minor-universal planar graphs without accumulation points
• Shorter Labeling Schemes for Planar Graphs
• Sparse universal graphs for planarity
• Universal geometric graphs
• A note on universal graphs for spanning trees
• Universality for graphs with bounded density
• Universality for graphs of bounded degeneracy
• Induced-universal graphs for graphs with bounded maximum degree
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs

This page was built for publication: Small universal graphs for bounded-degree planar graphs

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