Elimination of local bridges

 Access to full text

 Full (PDF)

1. BOOTH K. S.-LUEKER G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-trees, J. Comput. System Sci. 13 (1976), 335-379. (1976) MR0433962
2. CHIBA N.-NISHIZEKI T.-ABE S.-OZAWA T., A linear algorithm for embedding planar graphs using PQ-trees, J. Comput. System Sci. 30 (1985), 54-76. (1985) Zbl0605.68060MR0788831
3. COOK S. A.-RECKHOW R. A., Time bounded random access machines, J. Comput. System Sci. 7 (1976), 354-375. (1976) MR0327074
4. de FRAYSSEIX H.-ROSENSTIEHL P., A depth-first search characterization of planarity, Ann. Discrete Math. 13 (1982), 75-80. (1982) Zbl0497.05026MR0671906
5. GROSS J. L.-TUCKER T. W., Topological Graph Theory, Wiley-Interscience, New York, 1987. (1987) Zbl0621.05013MR0898434
6. HOPCROFT J. E.-TARJAN R. E., Efficient planarity testing, J. Assoc. Comput. Mach. 21 (1974), 549-568. (1974) Zbl0307.68025MR0359387
7. JUVAN M.-MARINČEK J.-MOHAR B., A linear time algorithm for embedding graphs in the torus, (Submitted). 
8. LEMPEL A.-EVEN S.-CEDERBAUM I., An algorithm for planarity testing of graphs, In: Theory of Graphs: International Symposium, Rome, July 1966 (P. Rosenstiehl, ed.), Gordon and Breach, New York, 1967, pp. 215-232. (1966) MR0220617
9. MOHAR B., Convex representations of maps on the torus and other flat surfaces, Discrete Comput. Geom. 11 (1994), 83-95. (1994) Zbl0791.05029MR1244891
10. MOHAR B., A linear time algorithm for embedding graphs in an arbitrary surface, SIAM J. Discrete Math. (To appear). Zbl0931.05025MR1666045
11. OHTSUKI T., The two disjoint paths problem and wire routing design, In: Graph Theory and Algorithms (N. Saito, T. Nishizeki, eds.), Lecture Notes in Comput. Sci. 108, Springer,New York, 1980, pp. 207-216. (1980) 
12. ROBERTSON N.-SEYMOUR P. D., An outline of a disjoint paths algorithm, In: Paths, Flows, and VLSI-Layout, (B. Korte, L. Lovasz, H. J. Promel, A. Schrijver, eds.), Springer-Verlag, Berlin, 267-292. Zbl0759.05055MR1083383
13. VOSS H.-J., Cycles and Bridges in Graphs, Kluwer, Dordrecht, 1991. (1991) Zbl0731.05031MR1131525
14. WILLIAMSON S. G., Embedding graphs in the plane - algorithmic aspects, Ann. Discrete Math. 6 (1980), 349-384. (1980) Zbl0451.05021MR0593547
15. WILLIAMSON S. G., Depth-first search and Kuratowski subgraphs, J. Assoc. Comput. Mach. 31 (1984), 681-693. (1984) Zbl0632.68063MR0819162