1.
Planar graph
–
In graph theory, a planar graph is a graph that can be embedded in the plane, i. e. it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other, such a drawing is called a plane graph or planar embedding of the graph. Every graph that can be drawn on a plane can be drawn on the sphere as well, plane graphs can be encoded by combinatorial maps. The equivalence class of topologically equivalent drawings on the sphere is called a planar map, although a plane graph has an external or unbounded face, none of the faces of a planar map have a particular status. Planar graphs generalize to graphs drawable on a surface of a given genus, in this terminology, planar graphs have graph genus 0, since the plane are surfaces of genus 0. See graph embedding for other related topics, a subdivision of a graph results from inserting vertices into edges zero or more times. Instead of considering subdivisions, Wagners theorem deals with minors, A finite graph is planar if, klaus Wagner asked more generally whether any minor-closed class of graphs is determined by a finite set of forbidden minors. This is now the Robertson–Seymour theorem, proved in a series of papers. In the language of this theorem, K5 and K3,3 are the forbidden minors for the class of planar graphs. In practice, it is difficult to use Kuratowskis criterion to decide whether a given graph is planar. However, there exist fast algorithms for this problem, for a graph with n vertices, for a simple, connected, planar graph with v vertices and e edges, the following simple conditions hold, Theorem 1. If v ≥3 then e ≤ 3v −6, Theorem 2, if v ≥3 and there are no cycles of length 3, then e ≤ 2v −4. In this sense, planar graphs are graphs, in that they have only O edges. The graph K3,3, for example, has 6 vertices,9 edges, therefore, by Theorem 2, it cannot be planar. Note that these theorems provide necessary conditions for planarity that are not sufficient conditions, if both theorem 1 and 2 fail, other methods may be used. As an illustration, in the graph given above, v =5, e =6 and f =3. If the second graph is redrawn without edge intersections, it has v =4, e =6 and f =4. In general, if the property holds for all graphs of f faces

2.
1-planar graph
–
1-planar graphs were first studied by Ringel, who showed that they can be colored with at most seven colors. Later, the number of colors needed to color these graphs. The example of the complete graph K6, which is 1-planar, however, the proof that six colors are always enough is more complicated. This can obviously be done using eight colors by applying the four color theorem to the graph and its dual graph separately. A vertex coloring of the graph corresponds to a vertex-face coloring of the original planar graph. This auxiliary graph is 1-planar, from which it follows that Ringels vertex-face coloring problem may also be solved with six colors, every 1-planar graph with n vertices has at most 4n −8 edges. However, unlike planar graphs, there exist maximal 1-planar graphs that have fewer than 4n −8 edges. A 1-planar graph is said to be an optimal 1-planar graph if it has exactly 4n −8 edges, in a 1-planar embedding of an optimal 1-planar graph, the uncrossed edges necessarily form a quadrangulation. Every quadrangulation gives rise to an optimal 1-planar graph in this way and it follows that every optimal 1-planar graph is Eulerian, that the minimum degree in such a graph is six, and that every optimal 1-planar graph has at least eight vertices of degree exactly six. Additionally, every optimal 1-planar graph is 4-vertex-connected, and every 4-vertex cut in such a graph is a cycle in the underlying quadrangulation. The graphs that have straight 1-planar drawings have a tighter bound of 4n −9 on the maximum number of edges. A complete classification of the 1-planar complete graphs, complete bipartite graphs, every complete bipartite graph of the form K2, n is 1-planar, as is every complete tripartite graph of the form K1,1, n. Other than these infinite sets of examples, the only complete multipartite 1-planar graphs are K6, K1,1,1,6, K1,1,2,3, K2,2,2,2, K1,1,1,2,2, and their subgraphs. The minimal non-1-planar complete multipartite graphs are K3,7, K4,5, K1,3,4, K2,3,3, and K1,1,1,1,3. For instance, the bipartite graph K3,6 is 1-planar because it is a subgraph of K1,1,1,6. It is NP-complete to test whether a graph is 1-planar. The problem is tractable when parameterized by cyclomatic number or by tree-depth. In contrast to Fárys theorem for graphs, not every 1-planar graph may be drawn 1-planarly with straight line segments for its edges

3.
Antiprism graph
–
In the mathematical field of graph theory, an antiprism graph is a graph that has one of the antiprisms as its skeleton. An n-sided antiprism has 2n vertices and 4n edges and they are regular, polyhedral, and also Hamiltonian graphs. The first graph in the sequence, the graph, has 6 vertices and 12 edges. Although geometrically the star polygons also form the faces of a different sequence of antiprisms, an antiprism graph is a special case of a circulant graph, Ci2n. Other infinite sequences of polyhedral graph formed in a way from polyhedra with regular-polygon bases include the prism graphs. Other vertex-transitive polyhedral graphs include the Archimedean graphs

4.
Apex graph
–
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph and it is an apex, not the apex because an apex graph may have more than one apex, for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex, the null graph is also counted as an apex graph even though it has no vertex to remove. Apex graphs are closed under the operation of taking minors, contracting any edge, or removing any edge or vertex, leads to another apex graph. For, if G is a graph with apex v, then any contraction or removal that does not involve v preserves the planarity of the remaining graph. If an edge incident to v is contracted, the effect on the graph is equivalent to the removal of the other endpoint of the edge. And if v itself is removed, any vertex may be chosen as the apex. By the Robertson–Seymour theorem, because they form a family of graphs. There are only finitely many graphs that are neither apex graphs nor have another non-apex graph as a minor and these graphs are forbidden minors for the property of being an apex graph. Any other graph G is a graph if and only if none of the forbidden minors is a minor of G. These forbidden minors include the seven graphs of the Petersen family, however, a complete description of them remains unknown. Despite the complete set of forbidden minors remaining unknown, it is possible to test whether a graph is an apex graph. If k is variable, however, the problem is NP-complete, every apex graph has chromatic number at most five, the underlying planar graph requires at most four colors by the four color theorem, and the remaining vertex needs at most one additional color. Jørgensen conjectured that every 6-vertex-connected graph that does not have K6 as a minor must be an apex graph, if this were proved, the Robertson–Seymour–Thomas result on the Hadwiger conjecture would be an immediate consequence. However, if false, it has finitely many counterexamples. A minor-closed family of graphs that has a graph as one of its forbidden minors is known as apex-minor-free. Apex-minor-free graph families obey a strengthened version of the structure theorem, leading to additional approximation algorithms for graph coloring. However, some of results can also be extended to arbitrary minor-closed graph families via structure theorems relating them to apex-minor-free graphs

5.
Apollonian network
–
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar graphs, the uniquely 4-colorable planar graphs. They are named after Apollonius of Perga, who studied a related circle-packing construction, in this way, the triangle containing the new vertex is subdivided into three smaller triangles, which may in turn be subdivided in the same way. The complete graphs on three and four vertices, K3 and K4, are both Apollonian networks, K3 is formed by starting with a triangle and not performing any subdivisions, while K4 is formed by making a single subdivision before stopping. The Goldner–Harary graph is an Apollonian network that forms the smallest non-Hamiltonian maximal planar graph, another more complicated Apollonian network was used by Nishizeki to provide an example of a 1-tough non-Hamiltonian maximal planar graph. As well as being defined by recursive subdivision of triangles, the Apollonian networks have several other equivalent mathematical characterizations and they are the chordal maximal planar graphs, the chordal polyhedral graphs, and the planar 3-trees. They are the uniquely 4-colorable planar graphs, and the graphs with a unique Schnyder wood decomposition into three trees. They are the planar graphs with treewidth three, a class of graphs that can be characterized by their forbidden minors or by their reducability under Y-Δ transforms. They are the planar graphs with degeneracy three. This forms an alternative characterization of the Apollonian networks, they are exactly the maximal planar graphs or equivalently the chordal polyhedral graphs. In an Apollonian network, every clique is a complete graph on four vertices, formed by choosing any vertex. Every minimal clique separator is one of the subdivided triangles, a chordal graph in which all maximal cliques and all minimal clique separators have the same size is a k-tree, and Apollonian networks are examples of 3-trees. Not every 3-tree is planar, but the planar 3-trees are exactly the Apollonian networks, every Apollonian network is also a uniquely 4-colorable graph. It is more difficult to prove, but also true, that every uniquely 4-colorable planar graph is an Apollonian network, therefore, Apollonian networks may also be characterized as the uniquely 4-colorable planar graphs. Apollonian networks also provide examples of planar graphs having as few k-colorings as possible for k >4, however, the planar partial 3-trees, subgraphs of Apollonian networks, are minor-closed. Therefore, according to the Robertson–Seymour theorem, they can be characterized by a number of forbidden minors. The Apollonian graphs are the graphs that do not have any of these four graphs as a minor. In every subgraph of an Apollonian network, the most recently added vertex has degree at most three, so Apollonian networks have degeneracy three

6.
Bidiakis cube
–
In the mathematical field of graph theory, the Bidiakis cube is a 3-regular graph with 12 vertices and 18 edges. The Bidiakis cube is a cubic Hamiltonian graph and can be defined by the LCF notation 4, the Bidiakis cube can also be constructed from a cube by adding edges across the top and bottom faces which connect the centres of opposite sides of the faces. The two additional edges need to be perpendicular to each other, with this construction, the Bidiakis cube is a polyhedral graph, and can be realized as a convex polyhedron. Therefore, by Steinitzs theorem, it is a 3-vertex-connected simple planar graph, the characteristic polynomial of the Bidiakis cube is 2