4-connected maximal planar graphs are 4-ordered (Q1850021)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | 4-connected maximal planar graphs are 4-ordered |
scientific article |
Statements
4-connected maximal planar graphs are 4-ordered (English)
0 references
2 December 2002
0 references
A graph \(G\) is said to be \(k\)-ordered if given any cyclic \(k\)-tuple of distinct vertices of \(G\), there is a circuit in \(G\) that encounters these vertices in the given cyclic order. It is shown that every 4-connected maximal planar graph is 4-ordered. If a 4-connected planar graph is not maximal planar, then it need not be 2-linked [\textit{H. A. Jung}, Math. Ann. 187, 95-103 (1970; Zbl 0184.27601)], in which case it would not be 4-ordered.
0 references
\(k\)-ordered
0 references
maximal planar
0 references