Maximal planar graphs of inscribable type and diagonal flips

Let \(G\) be a maximal planar graph, \(xy\) an edge of \(G\), and \(\{x,y,z\}\), \(\{x,y,w\}\) the vertex-sets of the two triangular faces incident to \(xy\). Then, if \(wz \not\in E(G)\), the operation of removing edge \(xy\) and adding the edge \(wz\) is called a diagonal flip. A theorem of Wagner states that given any two maximal planar graphs, one can be obtained from the other by performing a finite sequence of diagonal flips. Now, if \(G\) is a graph which can be realized by a 3-dimensional polytope inscribed in a sphere, then \(G\) is said to be of inscribable type. The authors prove that given any two maximal planar graphs of inscribable type and on more than four vertices, one can be obtained from the other by a finite sequence of diagonal flips such that all intermediate graphs are of inscribable type.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Maximal planar graphs of inscribable type and diagonal flips

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