Randomly planar graphs
type: Item
instance of: scholarly article
title: Randomly planar graphs
zbMATH Open document ID: 0918.05046
DOI: 10.1016/S0012-365X(97)00066-6
author: Daniel C. Isaksen
author: David Petrie Moulton
published in: Discrete Mathematics
publication date: 1999-08-10T00:00:00Z
review text: A graph \(G\) is randomly planar if every planar embedding of every connected subgraph \(H\) of \(G\) can be extended to a planar embedding of \(G\). Intuitively, a graph is randomly planar if a planar embedding of it can be built up in any manner whatsoever. A graph is planar-forbidden if it is the union of a cycle and a path of length at least three between two (possibly equal) vertices of the cycle. In this paper the authors show that a graph is randomly planar if and only if it contains no planar-forbidden subgraphs. They go on to show such graphs are exactly those where every edge-block is isomorphic to \(K_1\), \(C_n\), \(K_4\), \(K_{2,n}\) with \(n \geq 3 \), or \(K_{1,1,n}\) with \(n \geq 2\). They give a similar theorem for strongly randomly planar graphs, which are defined the same as randomly planar graphs except for the extra condition that embeddings of disconnected subgraphs \(H\) must also extend to embeddings of \(G\).
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1110028
zbMATH Keywords: planarity
zbMATH Keywords: forbidden subgraphs
zbMATH Keywords: planar embedding
zbMATH Keywords: planar-forbidden
zbMATH Keywords: randomly planar graphs
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
cites work: Randomly Traceable Graphs
cites work: A problem regarding the tracing of graphs
cites work: Randomly decomposable graphs
cites work: Randomly matchable graphs
full work available at URL: s0012-365x(97)00066-6
OpenAlex ID: W2083162741
description: scientific article; zbMATH DE number 1110028