Previous |  Up |  Next


Title: Elimination of local bridges (English)
Author: Juvan, Martin
Author: Marinček, Jože
Author: Mohar, Bojan
Language: English
Journal: Mathematica Slovaca
ISSN: 0139-9918
Volume: 47
Issue: 1
Year: 1997
Pages: 85-92
Category: math
MSC: 05C10
MSC: 05C85
MSC: 68R10
idZBL: Zbl 0958.05033
idMR: MR1476749
Date available: 2009-09-25T11:20:27Z
Last updated: 2012-08-01
Stable URL:
Reference: [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 0433962
Reference: [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. Zbl 0605.68060, MR 0788831
Reference: [3] COOK S. A.-RECKHOW R. A.: Time bounded random access machines.J. Comput. System Sci. 7 (1976), 354-375. MR 0327074
Reference: [4] de FRAYSSEIX H.-ROSENSTIEHL P.: A depth-first search characterization of planarity.Ann. Discrete Math. 13 (1982), 75-80. Zbl 0497.05026, MR 0671906
Reference: [5] GROSS J. L.-TUCKER T. W.: Topological Graph Theory.Wiley-Interscience, New York, 1987. Zbl 0621.05013, MR 0898434
Reference: [6] HOPCROFT J. E.-TARJAN R. E.: Efficient planarity testing.J. Assoc. Comput. Mach. 21 (1974), 549-568. Zbl 0307.68025, MR 0359387
Reference: [7] JUVAN M.-MARINČEK J.-MOHAR B.: A linear time algorithm for embedding graphs in the torus.(Submitted).
Reference: [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 0220617
Reference: [9] MOHAR B.: Convex representations of maps on the torus and other flat surfaces.Discrete Comput. Geom. 11 (1994), 83-95. Zbl 0791.05029, MR 1244891
Reference: [10] MOHAR B.: A linear time algorithm for embedding graphs in an arbitrary surface.SIAM J. Discrete Math. (To appear). Zbl 0931.05025, MR 1666045
Reference: [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.
Reference: [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. Zbl 0759.05055, MR 1083383
Reference: [13] VOSS H.-J.: Cycles and Bridges in Graphs.Kluwer, Dordrecht, 1991. Zbl 0731.05031, MR 1131525
Reference: [14] WILLIAMSON S. G.: Embedding graphs in the plane - algorithmic aspects.Ann. Discrete Math. 6 (1980), 349-384. Zbl 0451.05021, MR 0593547
Reference: [15] WILLIAMSON S. G.: Depth-first search and Kuratowski subgraphs.J. Assoc. Comput. Mach. 31 (1984), 681-693. Zbl 0632.68063, MR 0819162


Files Size Format View
MathSlov_47-1997-1_4.pdf 570.2Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo