plane graph



The term “plane graph” is used (with a slight bit of ambiguity) to refer to a crossing-free drawing of a graph, or more abstractly to an embedding of a graph into a surface of genus 0 (also called a planar map), or even more abstractly to a graph equipped with a cyclic ordering of the half-edges around each vertex which determines such an embedding up to isomorphism (see: combinatorial map). In any case, when the terminology is employed, it is usually meant to be distinguished from a “planar graph” as being a structure rather than a property (in the sense of stuff, structures, and properties), although sometimes the word “planar graph” is also used in the structure sense.


  • Sergei K. Lando and Alexander K. Zvonkin, Graphs on Surfaces and Their Applications, Springer, 2004.

  • Phillipe Flajolet, Robert Sedgewick?: Analytic Combinatorics. First Edition. Cambridge University Press. 2009. (See Chapter VII. 8.2)

Last revised on August 30, 2018 at 00:33:02. See the history of this page for a list of all contributions to it.