| 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:
|
http://hdl.handle.net/10338.dmlcz/136697 |
| . |
| 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 |
| . |
