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.



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

Revised: December 19, 2005.