Eades, Peter; Hong, Seok-Hee; Katoh, Naoki; Liotta, Giuseppe; Schweitzer, Pascal; Suzuki, Yusuke
A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. A 1-planar embedding of a graph G is maximal if no edge can be added without violating the 1-planarity of G. In this paper we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is...[Show more]
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.