Additional Key Words and Phrases: algorithm, complexity, depth-first search, embedding, genus, graph, palm tree, planarity, spanning tree
Selected papers that cite this one
- Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153-180, January 1994.
- Giuseppe Di Battista and Roberto Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956-997, October 1996.
- Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, and Roberto Tamassia. Optimal upward planarity testing of single-source digraphs. SIAM Journal on Computing, 27(1):132-169, February 1998.
- Jianer Chen. Algorithmic graph embeddings. Theoretical Computer Science, 181(2):247-266, 30 July 1997.
- Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky. A note on approximating graph genus. Information Processing Letters, 61(6):317-322, 28 March 1997.
- M. Chrobak and T. H. Payne. A linear-time algorithm for drawing a planar graph on a grid. Information Processing Letters, 54(4):241-246, 26 May 1995.
- Laurent Coupry. A simple linear algorithm for the edge-disjoint (s, t)-paths problem in undirected planar graphs. Information Processing Letters, 64(2):83-86, 28 October 1997.
- Artur Czumaj and Alan Gibbons. Guthrie's problem: new equivalences and rapid reductions. Theoretical Computer Science, 154(1):3-22, 22 January 1996.
- Narsingh Deo. Note on Hopcroft and Tarjan's planarity algorithm. Journal of the ACM, 23(1):74-75, January 1976.
- K. S. Easwarakumar, S. V. Krishnan, C. Pandu Rangan, and S. Seshadri. Optimal parallel algorithm for finding st-ambitus of a planar biconnected graph. Algorithmica, 15(3):242-255, March 1996.
- Shimon Even and Robert Endre Tarjan. Computing an st-numbering. Theoretical Computer Science, 2(3):339-344, September 1976.
- Greg N. Frederickson. Planar graph decomposition and all pairs shortest paths. Journal of the ACM, 38(1):162-204, January 1991.
- Stéphane Grumbach and Tova Milo. An algebra for pomsets. Accepted for publication in Information and Computation. Final manuscript received for publication November 25, 1998.
- Xin He. On floorplans of planar graphs. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 426-435, El Paso, Texas, 4-6 May 1997.
- Kurt Hoffman, Kurt Mehlhorn, Pierre Rosenstiehl, and Robert E. Tarjan. Sorting Jordan sequences in linear time using level-linked search trees. Information and Control, 68(1-3):170-184, January/February/March 1986.
- Michael D. Hutton and Anna Lubiw. Upward planar drawings of single-source acyclic digraphs. SIAM Journal on Computing, 25(2):291-311, April 1996.
- Goos Kant and Xin He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172(1-2):175-193, 10 February 1997.
- K. Mehlhorn and P. Mutzel. On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica, 16(2):233-242, August 1996.
- Gary L. Miller and Joseph (Seffi) Naor. Flow in planar graphs with multiple sources and sinks. SIAM Journal on Computing, 24(5):1002-1017, October 1995.
- B. Mishra. Bidirectional edges problem: Part I -- a simple algorithm. Algorithmica, 15(3):256-286, March 1996.
- Bojan Mohar. Embedding graphs in an arbitrary surface in linear time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 392-397, Philadelphia, Pennsylvania, 22-24 May 1996.
- Eugene Neufeld and Wendy Myrvold. Practical toroidality testing. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 574-580, New Orleans, Louisiana, 5-7 January 1997.
- Juha Nurmonen. On winning strategies with unary quantifiers. Journal of Logic and Computation, 6(6):779-798, December 1996.
- J. A. La Poutré Alpha-algorithms for incremental planarity testing (extended abstract). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 706-715, Montréal, Québec, Canada, 23-25 May 1994.
- Roberto Tamassia. On-line planar graph embedding. Journal of Algorithms, 21(2):201-239, September 1996.
- Karsten Weihe. Maximum (s, t)-flows in planar networks in O(|V| log |V|) time. Journal of Computer and System Sciences, 55(3):454-475, December 1997.
- Karsten Weihe. Edge-disjoint (s, t)-paths in undirected planar graphs in linear time. Journal of Algorithms, 23(1):121-138, April 1997.
Selected references
- Solomon W. Golomb and Leonard D. Baumert. Backtrack programming. Journal of the ACM, 12(4):516-524, October 1965.