Abstract | ||
---|---|---|
In this paper, we consider the problem of determining whether a given graph is a maximal planar graph or not. We show that a simple linear time algorithm can be designed based on canonical orderings. Our algorithm needs no sophisticated data structure and is significantly easy to implement compared with the existing planarity testing algorithms. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.ipl.2003.11.011 | Inf. Process. Lett. |
Keywords | Field | DocType |
canonical ordering,simple linear time algorithm,existing planarity testing algorithm,maximal planar graph,sophisticated data structure,simple recognition,planar graph,plane graph,data structure | Discrete mathematics,Combinatorics,Outerplanar graph,Planarity testing,Line graph,Cycle basis,Planar straight-line graph,Algorithm,Book embedding,Pathwidth,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
89 | 5 | 0020-0190 |
Citations | PageRank | References |
1 | 0.37 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hiroshi Nagamochi | 1 | 1513 | 174.40 |
Takahisa Suzuki | 2 | 2 | 2.41 |
Toshimasa Ishii | 3 | 110 | 17.03 |