pages 210-221
Listing All Plane Graphs
Publication type: Book Chapter
—
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(m
3) time per graph.
Found
Found
Top-30
Journals
|
1
2
3
4
|
|
|
Lecture Notes in Computer Science
4 publications, 80%
|
|
|
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
1 publication, 20%
|
|
|
1
2
3
4
|
Publishers
|
1
2
3
4
|
|
|
Springer Nature
4 publications, 80%
|
|
|
1 publication, 20%
|
|
|
1
2
3
4
|
- We do not take into account publications without a DOI.
- Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.