An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm
An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm
The book An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm was written by author Here you can read free online of An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm book, rate and share your impressions in comments. If you don't know what to write, just answer the question: Why is An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm a good or bad book?
Where can I read An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm for free?
In our eReader you can find the full English version of the book. Read An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm Online - link to read the book on full screen. Our eReader also allows you to upload and read Pdf, Txt, ePub and fb2 books. In the Mini eReder on the page below you can quickly view all pages of the book - Read Book An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm
In our eReader you can find the full English version of the book. Read An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm Online - link to read the book on full screen. Our eReader also allows you to upload and read Pdf, Txt, ePub and fb2 books. In the Mini eReder on the page below you can quickly view all pages of the book - Read Book An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm
What reading level is An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm book?
To quickly assess the difficulty of the text, read a short excerpt:
• Summary We presented a totally iterative version of Hopcroft and Tarjan's planarity testing algorithm (H-T algorithm). The control structure of our algorithm is so simple that it can be derived from one line formal specification. In H-T algorithm, the edges are visited in an order totally deter- mined by the depth first search. In our algorithm, the edges can be visited in any topological order of the DFS tree. In fact, our algorithm can be viewed as a topological sorting on the DFS tree comb...ined with some information propagation. Also, our algorithm allows some degree of parallelism: all the edges on the frontier of the DFS tree can be processed parallelly. H-T algo- rithm works on biconnected components of G, we do not need this condition.
The same idea of dependency graph mentioned in [4] can be used in our algorithm to actu- ally construct a planar embedding of G, also in linear lime.
• Appendix Proof of Theorem 5 We prove Theorem 5 by induction.
For backedges and dead edges, we need only prove iii, which is trivially true.
What to read after An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm?
You can find similar books in the "Read Also" column, or choose other free books by Jiazhen Cai to read onlineMoreLess
To quickly assess the difficulty of the text, read a short excerpt:
• Summary We presented a totally iterative version of Hopcroft and Tarjan's planarity testing algorithm (H-T algorithm). The control structure of our algorithm is so simple that it can be derived from one line formal specification. In H-T algorithm, the edges are visited in an order totally deter- mined by the depth first search. In our algorithm, the edges can be visited in any topological order of the DFS tree. In fact, our algorithm can be viewed as a topological sorting on the DFS tree comb...ined with some information propagation. Also, our algorithm allows some degree of parallelism: all the edges on the frontier of the DFS tree can be processed parallelly. H-T algo- rithm works on biconnected components of G, we do not need this condition.
The same idea of dependency graph mentioned in [4] can be used in our algorithm to actu- ally construct a planar embedding of G, also in linear lime.
• Appendix Proof of Theorem 5 We prove Theorem 5 by induction.
For backedges and dead edges, we need only prove iii, which is trivially true.
What to read after An Interative Version of Hopcroft And Tarjans Planarity Testing Algorithm?
You can find similar books in the "Read Also" column, or choose other free books by Jiazhen Cai to read onlineMoreLess
Write Review:
Guest
Read Also
7 / 10
8.2 / 10
User Reviews: