Editing Planar graph (section)

=== Other results ===

The [[four color theorem]] states that every planar graph is 4-[[graph coloring|colorable]] (i.e., 4-partite).

[[Fáry's theorem]] states that every simple planar graph admits a representation as a [[planar straight-line graph]]. A [[universal point set]] is a set of points such that every planar graph with ''n'' vertices has such an embedding with all vertices in the point set; there exist universal point sets of quadratic size, formed by taking a rectangular subset of the [[integer lattice]]. Every simple outerplanar graph admits an embedding in the plane such that all vertices lie on a fixed circle and all edges are straight line segments that lie inside the disk and don't intersect, so ''n''-vertex [[regular polygon]]s are universal for outerplanar graphs.

[[Scheinerman's conjecture]] (now a theorem) states that every planar graph can be represented as an [[intersection graph]] of [[line segment]]s in the plane.

The [[planar separator theorem]] states that every ''n''-vertex planar graph can be partitioned into two [[Glossary of graph theory#Subgraphs|subgraphs]] of size at most 2''n''/3 by the removal of O({{radic|''n''}}) vertices. As a consequence, planar graphs also have [[treewidth]] and [[branch-width]] O({{radic|''n''}}).

The planar product structure theorem states that every planar graph is a subgraph of the strong [[graph product]] of a graph of treewidth at most 8 and a path.<ref>{{citation
 | last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović
 | last2 = Joret | first2 = Gwenäel 
 | last3 = Micek | first3 = Piotr
 | last4 = Morin | first4 = Pat | author4-link = Pat Morin
 | last5 = Ueckerdt | first5 = Torsten
 | last6 = Wood | first6 = David R. | author6-link = David Wood (mathematician)
 | title = Planar graphs have bounded queue number
 | journal = Journal of the ACM
 | volume = 67
 | number = 4
 | pages = 22:1–22:38
 | doi = 10.1145/3385731
 | arxiv = 1904.04791
 | year = 2020}}</ref>
This result has been used to show that planar graphs have bounded [[queue number]], bounded [[Thue number|non-repetitive chromatic number]], and [[universal graph]]s of near-linear size.  It also has applications to vertex ranking<ref>{{citation
 | last1 = Bose | first1 = Prosenjit
 | last2 = Dujmović | first2 = Vida | author2-link = Vida Dujmović
 | last3 = Javarsineh | first3 = Mehrnoosh
 | last4 = Morin | first4 = Pat
 | title = Asymptotically optimal vertex ranking of planar graphs
 | arxiv = 2007.06455
 | year = 2020
}}</ref>
and ''p''-centered colouring<ref>{{citation
 | last1 = Dębski | first1 = Michał 
 | last2 = Felsner | first2 = Stefan 
 | last3 = Micek | first3 = Piotr 
 | last4 = Schröder | first4 = Felix
 | title = Improved Bounds for Centered Colorings
 | journal = Advances in Combinatorics 
 | arxiv = 1907.04586
 | year = 2021
| doi = 10.19086/aic.27351 
 | s2cid = 195874032 
 }}</ref>
of planar graphs.

For two planar graphs with ''v'' vertices, it is possible to determine in time O(''v'') whether they are [[graph theory|isomorphic]] or not (see also [[graph isomorphism problem]]).<ref>{{cite book |first1=I. S. |last1=Filotti |first2=Jack N. |last2=Mayer |chapter=A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus |title=Proceedings of the 12th Annual ACM Symposium on Theory of Computing |pages=236–243 |year=1980 |doi=10.1145/800141.804671 |isbn=978-0-89791-017-0|s2cid=16345164 |url=https://hal.inria.fr/inria-00076553/file/RR-0008.pdf }}</ref>

Any planar graph on n nodes has at most 8(n-2) maximal cliques,<ref>Wood, D. R. (2007). On the Maximum Number of Cliques in a Graph. ''Graphs and Combinatorics'', ''23''(3), 337–352. https://doi.org/10.1007/s00373-007-0738-8</ref> which implies that the class of planar graphs is a [[Graphs with few cliques|class with few cliques.]]