Apex graph

[4] Apex graphs are closed under the operation of taking minors: contracting any edge, or removing any edge or vertex, leads to another apex graph.

[13] If G is an apex graph with apex v, and τ is the minimum number of faces needed to cover all the neighbors of v in a planar embedding of G \ {v}, then G may be embedded onto a two-dimensional surface of genus τ – 1: simply add that number of bridges to the planar embedding, connecting together all the faces into which v must be connected.

When G \ {v} is 3-connected, his bound is within a constant factor of optimal: every surface embedding of G requires genus at least ⁠τ/160⁠.

However, it is NP-hard to determine the optimal genus of a surface embedding of an apex graph.

[14] By using SPQR trees to encode the possible embeddings of the planar part of an apex graph, it is possible to compute a drawing of the graph in the plane in which the only crossings involve the apex vertex, minimizing the total number of crossings, in polynomial time.

[15] However, if arbitrary crossings are allowed, it becomes NP-hard to minimize the number of crossings, even in the special case of apex graphs formed by adding a single edge to a planar graph.

[17] A drawing of this type may be obtained by drawing the planar part of the graph in a plane, placing the apex above the plane, and connecting the apex by straight-line edges to each of its neighbors.

A connected graph is YΔY-reducible if it can be reduced to a single vertex by a sequence of steps, each of which is a Δ-Y or Y-Δ transform, the removal of a self-loop or multiple adjacency, the removal of a vertex with one neighbor, and the replacement of a vertex of degree two and its two neighboring edges by a single edge.

However, Neil Robertson provided an example of an apex graph that is not YΔY-reducible.

It can be obtained by connecting an apex vertex to each of the degree-three vertices of a rhombic dodecahedron, or by merging two diametrally opposed vertices of a four-dimensional hypercube graph.

For instance, in the minor-minimal nonplanar graphs K5 and K3,3, any of the vertices can be chosen as the apex.

An abstract graph is said to be n-apex if it can be made planar by deleting n or fewer vertices.