Geodesic
Elimination of local bridges
Mathematica slovaca, Tome 47 (1997) no. 1, pp. 85-92
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 05C10, 05C85, 68R10 
@article{MASLO_1997_47_1_a3,
     author = {Juvan, Martin and Marin\v{c}ek, Jo\v{z}e and Mohar, Bojan},
     title = {Elimination of local bridges},
     journal = {Mathematica slovaca},
     pages = {85--92},
     year = {1997},
     volume = {47},
     number = {1},
     mrnumber = {1476749},
     zbl = {0958.05033},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MASLO_1997_47_1_a3/}
}
TY  - JOUR
AU  - Juvan, Martin
AU  - Marinček, Jože
AU  - Mohar, Bojan
TI  - Elimination of local bridges
JO  - Mathematica slovaca
PY  - 1997
SP  - 85
EP  - 92
VL  - 47
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MASLO_1997_47_1_a3/
LA  - en
ID  - MASLO_1997_47_1_a3
ER  - 
%0 Journal Article
%A Juvan, Martin
%A Marinček, Jože
%A Mohar, Bojan
%T Elimination of local bridges
%J Mathematica slovaca
%D 1997
%P 85-92
%V 47
%N 1
%U http://geodesic.mathdoc.fr/item/MASLO_1997_47_1_a3/
%G en
%F MASLO_1997_47_1_a3
Juvan, Martin; Marinček, Jože; Mohar, Bojan. Elimination of local bridges. Mathematica slovaca, Tome 47 (1997) no. 1, pp. 85-92. http://geodesic.mathdoc.fr/item/MASLO_1997_47_1_a3/

[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. | MR

[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. | MR | Zbl

[3] COOK S. A.-RECKHOW R. A.: Time bounded random access machines. J. Comput. System Sci. 7 (1976), 354-375. | MR

[4] de FRAYSSEIX H.-ROSENSTIEHL P.: A depth-first search characterization of planarity. Ann. Discrete Math. 13 (1982), 75-80. | MR | Zbl

[5] GROSS J. L.-TUCKER T. W.: Topological Graph Theory. Wiley-Interscience, New York, 1987. | MR | Zbl

[6] HOPCROFT J. E.-TARJAN R. E.: Efficient planarity testing. J. Assoc. Comput. Mach. 21 (1974), 549-568. | MR | Zbl

[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. | MR

[9] MOHAR B.: Convex representations of maps on the torus and other flat surfaces. Discrete Comput. Geom. 11 (1994), 83-95. | MR | Zbl

[10] MOHAR B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. (To appear). | MR | Zbl

[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.

[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. | MR | Zbl

[13] VOSS H.-J.: Cycles and Bridges in Graphs. Kluwer, Dordrecht, 1991. | MR | Zbl

[14] WILLIAMSON S. G.: Embedding graphs in the plane - algorithmic aspects. Ann. Discrete Math. 6 (1980), 349-384. | MR | Zbl

[15] WILLIAMSON S. G.: Depth-first search and Kuratowski subgraphs. J. Assoc. Comput. Mach. 31 (1984), 681-693. | MR | Zbl