Skip navigation
Skip navigation

Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)

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]

CollectionsANU Research Publications
Date published: 2012
Type: Conference paper
Source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI: 10.1007/978-3-642-36763-2_30


File Description SizeFormat Image
01_Eades_Testing_maximal_1-planarity_of_2012.pdf411.78 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