@article{MASLO_1997_47_1_a1,
author = {Mohar, Bojan},
title = {Face-width of embedded graphs},
journal = {Mathematica slovaca},
pages = {35--63},
year = {1997},
volume = {47},
number = {1},
mrnumber = {1476747},
zbl = {0958.05034},
language = {en},
url = {http://geodesic.mathdoc.fr/item/MASLO_1997_47_1_a1/}
}
Mohar, Bojan. Face-width of embedded graphs. Mathematica slovaca, Tome 47 (1997) no. 1, pp. 35-63. http://geodesic.mathdoc.fr/item/MASLO_1997_47_1_a1/
[1] ALTSCHULER A.: Hamiltonian circuits in some maps on the torus. Discrete Math. 1 (1972), 299-314. | MR
[2] ARCHDEACON D.: Densely embedded graphs. J. Combin, Theory Ser. B 54 (1992), 13-36. | MR | Zbl
[3] ARCHDEACON D.-RICHTER R. B.: Construction and classification of self-dual spherical polyhedra. J. Combin. Theory Ser. B 54 (1992), 37-63. | MR
[4] ARCHDEACON D.-HARTSFIELD N.-LITTLE C. H. C.: Non-Hamiltonian triangulations with large connectivity and representativity. J. Combin. Theory Ser. B 68 (1996), 45-55. | MR
[5] AUSLANDER L.-BROWN I. A.-YOUNGS J. W. T.: The imbedding of graphs in manifolds. J. Math. Mech. 12 (1963), 629-634. | MR | Zbl
[6] BARNETTE D.: Trees in polyhedral graphs. Canad. J. Math. 18 (1966), 731-736. | MR | Zbl
[7] BARNETTE D.: Generating the triangulations of the projective plane. J. Combin. Theory Ser. B 33 (1982), 222-230. | MR | Zbl
[8] BARNETTE D. W.: Generating closed 2-cell embeddings in the torus and the projective plane. Discrete Comput. Geom. 2 (1987), 233-247. | MR | Zbl
[9] BARNETTE D. W.: Decomposition theorems for the torus projective plane and Klein bottle. Discrete Math. 70 (1988), 1-16. | MR | Zbl
[10] BARNETTE D. W.: Unique embeddings of simple projective plane polyhedral maps. Israel J. Math. 67 (1989), 251-256. | MR | Zbl
[11] BARNETTE D. W.: Generating projective plane polyhedral maps. J. Combin. Theory Ser. B 51 (1991), 277-291. | MR | Zbl
[12] BARNETTE D. W.: The minimal projective plane polyhedral maps. In: Applied Geometry and Discrete Mathematics (P. Gritzmann, B. Sturmfels, eds.), Amer. Math. Soc, Providence, R.I., 1991, pp. 63-70. | MR | Zbl
[13] BARNETTE D. W.: n-chain embeddings in the projective plane, torus and Klein bottle. Preprint, 1991. | MR
[14] BARNETTE D. W.: 3-trees in polyhedral maps. Israel. J. Math. 79 (1992), 251-256. | MR | Zbl
[15] BARNETTE D.: 2-connected spanning subgraphs of planar 3-connected graphs. J. Combin. Theory Ser. B 61 (1994), 210-216. | MR | Zbl
[16] BARNETTE D. W.-RISKIN A.: Polyhedral and closed 2-cell embeddings in manifolds. Preprint, 1991.
[17] BENDER E. A.-GAO Z.-RICHMOND L. B.: Almost all rooted maps have large representativity. J. Graph Theory 18 (1994), 545-555. | MR | Zbl
[18] BONDY J. A.-MURTY U. S. R.: Graph Theory with Applications. North- Holland, New York, 1981.
[19] BRIGHTWELL G. R.-SCHEINERMAN E. R.: Representations of planar graphs. SIAM J. Discrete Math. 6 (1993), 214-229. | MR | Zbl
[20] BRUNET R.-ELLINGHAM M. N.-GAO Z.-METZLAR A.-RICHTER R. B.: Spanning planar subgraphs of graphs in the torus and Klein bottle. J. Combin. Theory Ser. B 65 (1995), 7-22. | MR | Zbl
[21] BRUNET R.-MOHAR B.-RICHTER R. B.: Separating and nonseparating disjoint homotopic cycles in graph embeddings. J. Combin. Theory Ser. B 66 (1996), 201-231. | MR | Zbl
[22] ELLINGHAM M. N.-GAO Z.: Spanning trees in locally planar triangulations. J. Combin. Theory Ser. B 61 (1994), 178-198. | MR | Zbl
[23] FIEDLER J. R.-HUNEKE J. P.-RICHTER R. B.-ROBERTSON N.: Computing the orientable genus of projective graphs. J. Graph Theory 20 (1995), 297-308. | MR | Zbl
[24] GAO Z. C.: 2-connected coverings of bounded degree in 3-connected graphs. J. Graph Theory 20 (1995), 327-338. | MR | Zbl
[25] GAO Z. C.-RICHMOND L. B- THOMASSEN C.: Irreducible triangulations and triangular embeddings on a surface. Research Report CORR 91 07, University of Waterloo, 1991.
[26] GAO Z. C.-RICHTER R. B.: 2-walks in circuit graphs. J. Combin. Theory Ser. B 62 (1994), 259-267. | MR | Zbl
[27] GAO Z.-RICHTER R. B.-SEYMOUR P. D.: Irreducible triangulations of surfaces. J. Combin. Theory Ser. B 68 (1996), 206-217. | MR | Zbl
[28] GAO Z. C.-RICHTER R. B.-YU X.: 2-walks in planar 3-connected graphs. Australas. J. Combin. 11 (1995), 117-122. | MR
[29] GAO Z. C,. WORMALD N. C.: Spanning Eulerian subgraphs of bounded degree in triangulations. Graphs Combin. 10 (1994), 123-131. | MR
[30] de GRAAF M.: Graphs and Curves on Surfaces. Ph. D. Thesis, University of Amsterdam, Amsterdam, 1994.
[31] de GRAAF M.-SCHRIJVER A.: Grid minors of graphs on the torus. J. Com- bin. Theory Ser. B 61 (1994), 57-62. | MR | Zbl
[32] GROSS J. L.-TUCKER T. W.: Topological Graph Theory. Wiley Interscience, New York, 1987. | MR | Zbl
[33] HUTCHINSON J.: On short noncontractible cycles in embedded graphs. SIAM J. Discrete Math. 1 (1988), 185-192. | MR | Zbl
[34] HUTCHINSON J.: On genus-reducing and planarizing algorithms for embedded graphs. In: Graphs and Algorithms. Contemp. Math. 89, Amer. Math. Soc, Providence, 1989, pp. 19-26. | MR | Zbl
[35] HUTCHINSON J. P.: Three-coloring graphs embedded on surfaces with all faces even-sided. J. Combin. Theory Ser. B 65 (1995), 139-155. | MR | Zbl
[36] JUVAN M.-MALNIC A.-MOHAR B.: Systems of curves on surfaces. J. Combin. Theory Ser. B 68 (1996), 7-22. | MR | Zbl
[37] LAVRENCHENKO S.: An infinite set of torus triangulations of connectivity 5 whose graphs are not uniquely embeddable in the torus. Discrete Math. 66 (1987), 299-301. | MR | Zbl
[38] LAWRENCHENKO S.: The variety of triangular embeddings of a graph in the projective plane. J. Combin. Theory Ser. B 54 (1992), 196-208. | MR
[39] LAWRENCENKO S.-NEGAMI S.: Constructing the graphs that triangulate both the torus and the Klein bottle. Preprint, 1994.
[40] LINS S.: A minimax theorem on circuits in projective graphs. J. Combin. Theory Ser. B 30 (1981), 253-262. | MR | Zbl
[41] MALNIC A.-MOHAR B.: Generating locally cyclic triangulations of surfaces. J. Combin. Theory Ser. B 56 (1992), 147-164. | MR | Zbl
[42] MALNIC A.-NEDELA R.: k-Minimal triangulations of surfaces. Acta Math. Univ. Comenian. 64 (1995), 57-76. | MR | Zbl
[43] MOHAR B.: Combinatorial local planarity and the width of graph embeddings. Canad. J. Math. 44 (1992), 1272-1288. | MR | Zbl
[44] MOHAR B.: Uniqueness and minimality of large face-width embeddings of graphs. Combinatorica 15 (1995), 541-556. | MR | Zbl
[45] MOHAR B.: Apex graphs with embeddings of face-width three. Discrete Math. (To appear). | MR | Zbl
[46] MOHAR B.: On the orientable genus of graphs with bounded nonorientable genus. Manuscript, 1995.
[47] MOHAR B.-ROBERTSON N.: Disjoint essential circuits in toroidal maps. In: Planar Graphs (W. T. Trotter, ed.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 9, Amer. Math. Soc, Providence, R.I., 1993, pp. 109 130. | MR | Zbl
[48] MOHAR B.-ROBERTSON N.: Disjoint essential cycles. J. Combin. Theory Ser. B 68 (1996), 324-349. | MR | Zbl
[49] MOHAR B.-ROBERTSON N.: Planar graphs on nonplanar surfaces. J. Combin. Theory Ser. B 68 (1996), 87-111. | MR | Zbl
[50] MOHAR B.-ROBERTSON N.-VITRAY R. P.: Planar graphs on the projective plane. Discrete Math. 149 (1996), 141-157. | MR | Zbl
[51] MOHAR B.-ROSENSTIEHL P.: A flow approach to upward drawings of toroidal maps. In: Graph Drawing (R. Tamassia, I. G. Tollis, eds.), Lecture Notes in Comput. Sci. 894, Springer, New York, 1995, pp. 33-39. | MR
[52] MOHAR B.-THOMASSEN C.: Graphs on Surfaces. Johns Hopkins Univ. Press (To appear). | MR | Zbl
[53] NAKAMOTO A.-OTA K.: Vote on irreducible triangulations of surfaces. J. Graph Theory 20 (1995), 227-233. | MR
[54] NEGAMI S.: Uniqueness and faithfulness of embedding of toroidal graphs. Discrete Math. 44 (1983), 161-180. | MR | Zbl
[55] NEGAMI S.: Unique and faithful embeddings of projective-planar graphs. J. Graph Theory 9 (1985), 235-243. | MR | Zbl
[56] NEGAMI S.: Re-embedding of projective-planar graphs. J. Combin. Theory Ser. B 44 (1988), 276-299. | MR | Zbl
[57] PRZYTYCKA T.-PRZYTYCKI J. H.: A simple construction of high representativity triangulations. Preprint, 1993. | MR
[58] RANDBY S. P.: Minimal embeddings in the projective plane. Preprint, 1995. | MR
[59] RICHTER R. B.-VITRAY R.: On the existence of essential cycles in embedded graphs. Preprint, 1992.
[60] RICHTER R. B.-VITRAY R.: On essential and inessential polygons in embedded graphs. Preprint, 1994. | MR
[61] RISKIN A.: On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle. Preprint, 1994. | MR
[62] RISKIN A.-BARNETTE D. W.: On the noninterpolation of polyhedral maps. Discrete Math. 131 (1994), 211-219. | MR | Zbl
[63] ROBERTSON N.-SEYMOUR P. D.: Graph minors. VII. Disjoint paths on a surface. J. Combin. Theory Ser. B 45 (1988), 212-254. | MR | Zbl
[64] ROBERTSON N.-SEYMOUR P. D.: Graph minors. XX. Wagner's conjecture. (In preparation). | Zbl
[65] ROBERTSON N.-SEYMOUR P. D.-THOMAS R.: A survey of linkless embeddings. In: Graph Structure Theory (Seattle, WA, 1991). Contemp. Math. 147,Amer. Math. Soc, Providence, RI, 1993, pp. 125-136. | MR
[66] ROBERTSON N.-THOMAS R.: On the orientable genus of graphs embedded in the Klein bottle. J. Graph Theory 15 (1991), 407-419. | MR | Zbl
[67] ROBERTSON N.-VITRAY R. P.: Represent ativity of surface embeddings. In: Paths, Flows, and VLSI-Layout (B. Korte, L. Lovasz, H. J. Promel, A. Schrijver, eds.), Springer-Verlag, Berlin, 1990, pp. 293-328. | MR
[68] ROBERTSON N.-ZHA X.-ZHAO Y.: On the uniqueness of embeddings of graphs in the torus. Preprint, 1995.
[69] SCHRIJVER A.: Homotopic routing methods. In: Paths, Flows, and VLSI-Layout (B. Korte, L. Lovasz, H. J. Promel, A. Schrijver, eds.), Springer-Verlag, Berlin, 1990, pp. 329-371. | MR | Zbl
[70] SCHRIJVER A.: Disjoint circuits of prescribed homotopies in a graph on a compact surface. J. Combin. Theory Ser. B 51 (1991), 127-159. | MR | Zbl
[71] SCHRIJVER A.: Decomposition of graphs on surfaces and a homotopic circulation theorem. J. Combin. Theory Ser. B 51 (1991), 161-210. | MR | Zbl
[72] SCHRIJVER A.: Circuits in graphs embedded on the torus. Discrete Math. 106/107 (1992), 415-433. | MR | Zbl
[73] SCHRIJVER A.: On the uniqueness of kernels. J. Combin. Theory Ser. B 55 (1992), 146-160. | MR | Zbl
[74] SCHRIJVER A.: Graphs on the torus and geometry of numbers. J. Combin. Theory Ser. B 58 (1993), 147-158. | MR | Zbl
[75] SCHRIJVER A.: Classification of minimal graphs of given face-width on the torus. J. Combin. Theory Ser. B 61 (1994), 217-236. | MR | Zbl
[76] SEYMOUR P. D.-THOMAS R.: Uniqueness of highly representative surface embeddings. J. Combin. Theory Ser. B (To appear). | MR | Zbl
[77] THOMAS R.-YU X.: 4-connected projective planar graphs are Hamiltonian. J. Combin. Theory Ser. B 62 (1994), 114-132. | MR | Zbl
[78] THOMAS R.-YU X.: 5-connected toroidal graphs are Hamiltonian. J. Combin. Theory Ser. B 69 (1997), 79-96. | MR
[79] THOMASSEN C.: The graph genus problem is NP-complete. J. Algorithms 10 (1989), 568-576. | MR | Zbl
[80] THOMASSEN C.: Embeddings of graphs with no short noncontractible cycles. J. Combin. Theory Ser. B 48 (1990), 155-177. | MR | Zbl
[81] THOMASSEN C.: Triangulating a surface with a prescribed graph. J. Combin. Theory Ser. B 57 (1993), 196-206. | MR | Zbl
[82] THOMASSEN C.: Five-coloring maps on surfaces. J. Combin. Theory Ser. B 59 (1993), 89-105. | MR | Zbl
[83] THOMASSEN C.: Trees in triangulations. J. Combin. Theory Ser. B 60 (1994), 56-62. | MR | Zbl
[84] TUTTE W. T.: A theorem on planar graphs. Trans. Amer. Math. Soc. 82 (1956), 99-116. | MR | Zbl
[85] VITRAY R.: The 2- and ^3-representative projective planar embeddings. J. Combin. Theory Ser. B 54 (1992), 1-12. | MR
[86] VITRAY R. P.: Representativity and flexibility on the projective plane. In: Graph Structure Theory (Seattle, WA, 1991). Contemp. Math. 147, Amer. Math. Soc, Providence, RI, 1993, pp. 341-347. | MR
[87] WHITNEY H.: 2-isomorphic graphs. Amer. J. Math. 55 (1933), 245-254. | MR | Zbl
[88] YU X.: Disjoint paths, planarizing cycles, and k-walks. Preprint, 1993.
[89] ZHA X. Y.-ZHAO Y.: On nonnull separating circuits in embedded graphs. In: Graph Structure Theory (Seattle, WA, 1991). Contemp. Math. 147, Amer. Math. Soc, Providence, RI, 1993, pp. 349-362. | MR