Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
References:
[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
[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 0788831 | Zbl 0605.68060
[3] COOK S. A.-RECKHOW R. A.: Time bounded random access machines. J. Comput. System Sci. 7 (1976), 354-375. MR 0327074
[4] de FRAYSSEIX H.-ROSENSTIEHL P.: A depth-first search characterization of planarity. Ann. Discrete Math. 13 (1982), 75-80. MR 0671906 | Zbl 0497.05026
[5] GROSS J. L.-TUCKER T. W.: Topological Graph Theory. Wiley-Interscience, New York, 1987. MR 0898434 | Zbl 0621.05013
[6] HOPCROFT J. E.-TARJAN R. E.: Efficient planarity testing. J. Assoc. Comput. Mach. 21 (1974), 549-568. MR 0359387 | Zbl 0307.68025
[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 0220617
[9] MOHAR B.: Convex representations of maps on the torus and other flat surfaces. Discrete Comput. Geom. 11 (1994), 83-95. MR 1244891 | Zbl 0791.05029
[10] MOHAR B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. (To appear). MR 1666045 | Zbl 0931.05025
[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 1083383 | Zbl 0759.05055
[13] VOSS H.-J.: Cycles and Bridges in Graphs. Kluwer, Dordrecht, 1991. MR 1131525 | Zbl 0731.05031
[14] WILLIAMSON S. G.: Embedding graphs in the plane - algorithmic aspects. Ann. Discrete Math. 6 (1980), 349-384. MR 0593547 | Zbl 0451.05021
[15] WILLIAMSON S. G.: Depth-first search and Kuratowski subgraphs. J. Assoc. Comput. Mach. 31 (1984), 681-693. MR 0819162 | Zbl 0632.68063
Search
Partner of
