## Apex number of the graph

Let us say that a graph is k-*apex* if it contains a set of at most k
vertices whose removal yields a planar graph. We define the *apex number*
of a graph G as the minimum k for which G is k-apex.

It is easy to check in quadratic time if a graph is 1-apex - simply test for
each vertex v, if G - v is planar.

**Problem 1:** Find
a subquadratic algorithm for testing if a given graph is 1-planar.

It is also easy to check in cubic time if G is 2-apex by testing planarity of
all 2-vertex-deleted subgraphs. More interestingly, there is a cubic time
algorithm for testing if G is k-apex for any fixed value of k. This follows from
Robertson and Seymour's theory of graph minors since the class of all k-apex
graphs is minor-closed.

**Problem 2:** If
k
is a constant, find a linear time algorithm for testing if a given graph is
k-apex.

Both problems are proposed jointly by myself and Sergio Cabello.

Bibliography:

[1]

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: December 19, 2005.