An outerplanar graph is a graph that can be embedded in the plane such that all vertices lie on the outer face. Outerplanar graphs are planar and, by their definition, connected graphs. A graph has book thickess 1 iff is is a non-empty outerplanar graph.
The complete graph and complete bipartite
graph
are planar, but not outerplanar (West 2000, p. 240).
In fact, a graph is outerplanar iff it contains no subgraph
homeomorphic to the complete graph
or complete bipartite
graph
(Skiena 1990, p. 251, with
corrected to
).
A graph is outerplanar iff the graph formed by adding a new vertex connected to each of the original vertices is a planar graph (Felsner 2004).
An outerplanar graph on vertices is Hamiltonian iff it is biconnected,
in which case the vertices of outer face comprise a unique Hamiltonian
cycle.
Every outerplanar graph is 3-colorable.