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