Eades, PeterHong, Seok-HeeKatoh, NaokiLiotta, GiuseppeSchweitzer, PascalSuzuki, Yusuke2015-12-130304-3975http://hdl.handle.net/1885/77885A 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. In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if additionA linear time algorithm for testing maximal 1-planarity of graphs with a rotation system201310.1016/j.tcs.2013.09.0292015-12-11