 |
| Home | Issues | About JGAA | Instructions for Authors |
|
Special Issue on Selected Papers from the Second International Workshop on Algorithms and
Computation, WALCOM 2008
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.
|
Submitted: January 2008.
Reviewed: June 2008.
Revised: July 2008.
Accepted: November 2008.
Final: December 2008.
Published: February 2009.
Communicated by
Md. Saidur Rahman
|
Journal publisher
|
Journal network
|
Journal Supporters
|
