Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00174 Listing All Plane Graphs Katsuhisa Yamanaka and Shin-ichi Nakano Vol. 13, no. 1, pp. 5-18, 2009. Regular paper Abstract In this paper we give a simple algorithm to generate all connected rooted plane graphs with at most m edges. A rooted" plane graph is a plane graph with one designated (directed) edge on the outer face. The algorithm uses O(m) space and generates such graphs in O(1) time per graph on average without duplications. The algorithm does not output the entire graph but the difference from the previous graph. By modifying the algorithm we can generate all connected (non-rooted) plane graphs with at most m edges in O(m3) time per graph.
|
Reviewed: June 2008. Final: December 2008. Revised: July 2008. Accepted: November 2008. Published: February 2009. Submitted: January 2008. Communicated by Md. Saidur Rahman |
| Journal of Graph Algorithms and Applications |