Skip navigation
Skip navigation

A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system

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. In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if addition

CollectionsANU Research Publications
Date published: 2013
Type: Journal article
Source: Theoretical Computer Science
DOI: 10.1016/j.tcs.2013.09.029


File Description SizeFormat Image
01_Eades_A_linear_time_algorithm_for_2013.pdf254.24 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator