Sparse universal graphs for planarity
Louis Esperet, Gwenaël Joret, Pat Morin
Abstract
Abstract We show that for every integer , there exists a graph with vertices and edges such that every ‐vertex planar graph is isomorphic to a subgraph of . The best previous bound on the number of edges was , proved by Babai, Chung, Erdős, Graham, and Spencer in 1982. We then show that for every integer , there is a graph with vertices and edges that contains induced copies of every ‐vertex planar graph. This significantly reduces the number of edges in a recent construction of the authors with Dujmović, Gavoille, and Micek.
Topics & Concepts
CombinatoricsMathematicsPlanarity testingPlanar graphWheel graphVertex (graph theory)Hypercube graphDiscrete mathematicsGraphBook embeddingGraph powerLine graphPathwidthAdvanced Graph Theory ResearchLimits and Structures in Graph TheoryComputational Geometry and Mesh Generation