A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs

1. F. Bao and Y. Igarashi, Reliable broadcasting in product networks with Byzantine faults, Proc. 26th Annual International Symposium on Fault-Tolelant Computing (FTCS’96) (1996) 262–271.

   Google Scholar 

2. G. Di Battista, R. Tamassia and L. Vismara, Output-sensitive reporting of disjoint paths, Technical Report CS-96-25, Department of Computer Science, Brown University (1996).

   Google Scholar 

3. G. Di Battista, R. Tamassia and L. Vismara, Output-sensitive reporting of disjoint paths, Algorithmica, 23(1999) 302–340.

   Article  MATH  MathSciNet  Google Scholar 

4. M. Chrobak and G. Kant, Convex grid drawings of 3-connected planar graphs, Technical Report RUU-CS-93-45, Department of Computer Science, Utrecht University (1993).

   Google Scholar 

5. M. Chrobak and G. Kant, Convex grid drawings of 3-connected planar graphs, International Journal of Computational Geometry and Applications, 7 (1997) 211–223.

   Article  MathSciNet  Google Scholar 

6. J. Cheriyan and S. N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, J. Algorithms, 9 (1988) 507–537.

   Article  MATH  MathSciNet  Google Scholar 

7. D. Dolev, J. Y. Halpern, B. Simons and R. Strong, A new look at fault tolerant network routing, Proc. 16th Annual ACM Symposium on Theory of Computing (1984) 526–535.

   Google Scholar 

8. S. Even, Graph Algorithms, Computer Science Press, Potomac (1979).

   Google Scholar 

9. A. Huck, Independent trees in graphs, Graphs and Combinatorics, 10(1994) 29–45.

   Article  MATH  MathSciNet  Google Scholar 

10. A. Huck, Independent trees in planar graphs, Graphs and Combinatorics, 15 (1999) 29–77.

    Article  MATH  MathSciNet  Google Scholar 

11. A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation, 79 (1988) 43–59.

    Article  MATH  MathSciNet  Google Scholar 

12. C. Kant, Drawing planar graphs using the cononical ordering, Algorithmica, 16 (1996) 4–32.

    Article  MATH  MathSciNet  Google Scholar 

13. G. Kant and X. He, Two algorithms for _nding rectangular duals of planar graphs, Proc. 19th Workshop on Graph-Theoretic Concepts in Computer Science (WG’93), Lect. Notes in Comp. Sci., 790, Springer (1994) 396–410.

    Google Scholar 

14. S. Khuller and B. Schieber, On independent spanning trees, Information Processing Letters, 42 (1992) 321–323.

    Article  MATH  MathSciNet  Google Scholar 

15. K. Miura, D. Takahashi, S. Nakano and T. Nishizeki, A Linear-Time Algorithm to Find Four Independent Spanning Trees in Four-Connected Planar Graphs, WG’98, Lect. Notes in Comp. Sci., 1517, Springer (1998) 310–323.

    Google Scholar 

16. S. Nakano, M. S. Rahman and T. Nishizeki, A linear time algorithm for four-partitioning four-connected planar graphs, Information Processing Letters, 62 (1997) 315–322.

    Article  MathSciNet  Google Scholar 

17. K. Obokata, Y. Iwasaki, F. Bao and Y. Igarashi, Independent spanning trees of product graphs and their construction, Proc. 22nd Workshop on Graph-Theoretic Concepts in Computer Science (WG’96), Lect. Notes in Comp. Sci., 1197 (1996) 338–351.

    Google Scholar 

18. W. Schnyder, Embedding planar graphs on the grid, Proc. 1st Annual ACMSIAM Symp. on Discrete Algorithms, San Francisco (1990) 138–148

    Google Scholar 

19. D. B. West, Introduction to Graph Teory, Prentice Hall (1996)

    Google Scholar 

20. A. Zehavi and A. Itai, Three tree-paths, J. Graph Theory, 13 (1989) 175–188.

    Article  MATH  MathSciNet  Google Scholar 

Download references