| Title:
|
Face-width of embedded graphs (English) |
| Author:
|
Mohar, Bojan |
| Language:
|
English |
| Journal:
|
Mathematica Slovaca |
| ISSN:
|
0139-9918 |
| Volume:
|
47 |
| Issue:
|
1 |
| Year:
|
1997 |
| Pages:
|
35-63 |
| . |
| Category:
|
math |
| . |
| MSC:
|
05C10 |
| idZBL:
|
Zbl 0958.05034 |
| idMR:
|
MR1476747 |
| . |
| Date available:
|
2009-09-25T11:20:09Z |
| Last updated:
|
2012-08-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133334 |
| . |
| Reference:
|
[1] ALTSCHULER A.: Hamiltonian circuits in some maps on the torus.Discrete Math. 1 (1972), 299-314. MR 0297597 |
| Reference:
|
[2] ARCHDEACON D.: Densely embedded graphs.J. Combin, Theory Ser. B 54 (1992), 13-36. Zbl 0694.05024, MR 1142262 |
| Reference:
|
[3] ARCHDEACON D.-RICHTER R. B.: Construction and classification of self-dual spherical polyhedra.J. Combin. Theory Ser. B 54 (1992), 37-63. MR 1142263 |
| Reference:
|
[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 1405705 |
| Reference:
|
[5] AUSLANDER L.-BROWN I. A.-YOUNGS J. W. T.: The imbedding of graphs in manifolds.J. Math. Mech. 12 (1963), 629-634. Zbl 0115.40804, MR 0151959 |
| Reference:
|
[6] BARNETTE D.: Trees in polyhedral graphs.Canad. J. Math. 18 (1966), 731-736. Zbl 0141.21401, MR 0195753 |
| Reference:
|
[7] BARNETTE D.: Generating the triangulations of the projective plane.J. Combin. Theory Ser. B 33 (1982), 222-230. Zbl 0509.52007, MR 0693361 |
| Reference:
|
[8] BARNETTE D. W.: Generating closed 2-cell embeddings in the torus and the projective plane.Discrete Comput. Geom. 2 (1987), 233-247. Zbl 0614.51008, MR 0892170 |
| Reference:
|
[9] BARNETTE D. W.: Decomposition theorems for the torus projective plane and Klein bottle.Discrete Math. 70 (1988), 1-16. Zbl 0654.05024, MR 0943718 |
| Reference:
|
[10] BARNETTE D. W.: Unique embeddings of simple projective plane polyhedral maps.Israel J. Math. 67 (1989), 251-256. Zbl 0694.05030, MR 1026567 |
| Reference:
|
[11] BARNETTE D. W.: Generating projective plane polyhedral maps.J. Combin. Theory Ser. B 51 (1991), 277-291. Zbl 0722.05029, MR 1099077 |
| Reference:
|
[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. Zbl 0803.52008, MR 1116338 |
| Reference:
|
[13] BARNETTE D. W.: n-chain embeddings in the projective plane, torus and Klein bottle.Preprint, 1991. MR 1119930 |
| Reference:
|
[14] BARNETTE D. W.: 3-trees in polyhedral maps.Israel. J. Math. 79 (1992), 251-256. Zbl 0770.05041, MR 1248916 |
| Reference:
|
[15] BARNETTE D.: 2-connected spanning subgraphs of planar 3-connected graphs.J. Combin. Theory Ser. B 61 (1994), 210-216. Zbl 0812.05015, MR 1280608 |
| Reference:
|
[16] BARNETTE D. W.-RISKIN A.: Polyhedral and closed 2-cell embeddings in manifolds.Preprint, 1991. |
| Reference:
|
[17] BENDER E. A.-GAO Z.-RICHMOND L. B.: Almost all rooted maps have large representativity.J. Graph Theory 18 (1994), 545-555. Zbl 0809.05060, MR 1292974 |
| Reference:
|
[18] BONDY J. A.-MURTY U. S. R.: Graph Theory with Applications.North- Holland, New York, 1981. |
| Reference:
|
[19] BRIGHTWELL G. R.-SCHEINERMAN E. R.: Representations of planar graphs.SIAM J. Discrete Math. 6 (1993), 214-229. Zbl 0782.05026, MR 1215229 |
| Reference:
|
[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. Zbl 0837.05049, MR 1347338 |
| Reference:
|
[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. Zbl 0855.05048, MR 1376046 |
| Reference:
|
[22] ELLINGHAM M. N.-GAO Z.: Spanning trees in locally planar triangulations.J. Combin. Theory Ser. B 61 (1994), 178-198. Zbl 0802.05033, MR 1280606 |
| Reference:
|
[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. Zbl 0837.05051, MR 1355428 |
| Reference:
|
[24] GAO Z. C.: 2-connected coverings of bounded degree in 3-connected graphs.J. Graph Theory 20 (1995), 327-338. Zbl 0838.05034, MR 1355432 |
| Reference:
|
[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. |
| Reference:
|
[26] GAO Z. C.-RICHTER R. B.: 2-walks in circuit graphs.J. Combin. Theory Ser. B 62 (1994), 259-267. Zbl 0807.05027, MR 1305052 |
| Reference:
|
[27] GAO Z.-RICHTER R. B.-SEYMOUR P. D.: Irreducible triangulations of surfaces.J. Combin. Theory Ser. B 68 (1996), 206-217. Zbl 0863.05029, MR 1417796 |
| Reference:
|
[28] GAO Z. C.-RICHTER R. B.-YU X.: 2-walks in planar 3-connected graphs.Australas. J. Combin. 11 (1995), 117-122. MR 1327325 |
| Reference:
|
[29] GAO Z. C,. WORMALD N. C.: Spanning Eulerian subgraphs of bounded degree in triangulations.Graphs Combin. 10 (1994), 123-131. MR 1289970 |
| Reference:
|
[30] de GRAAF M.: Graphs and Curves on Surfaces.Ph. D. Thesis, University of Amsterdam, Amsterdam, 1994. |
| Reference:
|
[31] de GRAAF M.-SCHRIJVER A.: Grid minors of graphs on the torus.J. Com- bin. Theory Ser. B 61 (1994), 57-62. Zbl 0809.05037, MR 1275263 |
| Reference:
|
[32] GROSS J. L.-TUCKER T. W.: Topological Graph Theory.Wiley Interscience, New York, 1987. Zbl 0621.05013, MR 0898434 |
| Reference:
|
[33] HUTCHINSON J.: On short noncontractible cycles in embedded graphs.SIAM J. Discrete Math. 1 (1988), 185-192. Zbl 0663.05025, MR 0941349 |
| Reference:
|
[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. Zbl 0682.68049, MR 1006473 |
| Reference:
|
[35] HUTCHINSON J. P.: Three-coloring graphs embedded on surfaces with all faces even-sided.J. Combin. Theory Ser. B 65 (1995), 139-155. Zbl 0828.05029, MR 1347344 |
| Reference:
|
[36] JUVAN M.-MALNIC A.-MOHAR B.: Systems of curves on surfaces.J. Combin. Theory Ser. B 68 (1996), 7-22. Zbl 0859.57014, MR 1405702 |
| Reference:
|
[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. Zbl 0618.05019, MR 0900052 |
| Reference:
|
[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 1152447 |
| Reference:
|
[39] LAWRENCENKO S.-NEGAMI S.: Constructing the graphs that triangulate both the torus and the Klein bottle.Preprint, 1994. |
| Reference:
|
[40] LINS S.: A minimax theorem on circuits in projective graphs.J. Combin. Theory Ser. B 30 (1981), 253-262. Zbl 0401.05067, MR 0624541 |
| Reference:
|
[41] MALNIC A.-MOHAR B.: Generating locally cyclic triangulations of surfaces.J. Combin. Theory Ser. B 56 (1992), 147-164. Zbl 0723.05053, MR 1186752 |
| Reference:
|
[42] MALNIC A.-NEDELA R.: k-Minimal triangulations of surfaces.Acta Math. Univ. Comenian. 64 (1995), 57-76. Zbl 0921.05029, MR 1360987 |
| Reference:
|
[43] MOHAR B.: Combinatorial local planarity and the width of graph embeddings.Canad. J. Math. 44 (1992), 1272-1288. Zbl 0777.05052, MR 1192418 |
| Reference:
|
[44] MOHAR B.: Uniqueness and minimality of large face-width embeddings of graphs.Combinatorica 15 (1995), 541-556. Zbl 0838.05041, MR 1364026 |
| Reference:
|
[45] MOHAR B.: Apex graphs with embeddings of face-width three.Discrete Math. (To appear). Zbl 0891.05026, MR 1477290 |
| Reference:
|
[46] MOHAR B.: On the orientable genus of graphs with bounded nonorientable genus.Manuscript, 1995. |
| Reference:
|
[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. Zbl 0792.05046, MR 1221805 |
| Reference:
|
[48] MOHAR B.-ROBERTSON N.: Disjoint essential cycles.J. Combin. Theory Ser. B 68 (1996), 324-349. Zbl 0861.05038, MR 1417805 |
| Reference:
|
[49] MOHAR B.-ROBERTSON N.: Planar graphs on nonplanar surfaces.J. Combin. Theory Ser. B 68 (1996), 87-111. Zbl 0856.05027, MR 1405707 |
| Reference:
|
[50] MOHAR B.-ROBERTSON N.-VITRAY R. P.: Planar graphs on the projective plane.Discrete Math. 149 (1996), 141-157. Zbl 0849.05023, MR 1375105 |
| Reference:
|
[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 1337505 |
| Reference:
|
[52] MOHAR B.-THOMASSEN C.: Graphs on Surfaces.Johns Hopkins Univ. Press (To appear). Zbl 1230.05133, MR 1844449 |
| Reference:
|
[53] NAKAMOTO A.-OTA K.: Vote on irreducible triangulations of surfaces.J. Graph Theory 20 (1995), 227-233. MR 1348564 |
| Reference:
|
[54] NEGAMI S.: Uniqueness and faithfulness of embedding of toroidal graphs.Discrete Math. 44 (1983), 161-180. Zbl 0508.05033, MR 0689809 |
| Reference:
|
[55] NEGAMI S.: Unique and faithful embeddings of projective-planar graphs.J. Graph Theory 9 (1985), 235-243. Zbl 0578.05017, MR 0797512 |
| Reference:
|
[56] NEGAMI S.: Re-embedding of projective-planar graphs.J. Combin. Theory Ser. B 44 (1988), 276-299. Zbl 0609.05033, MR 0941437 |
| Reference:
|
[57] PRZYTYCKA T.-PRZYTYCKI J. H.: A simple construction of high representativity triangulations.Preprint, 1993. MR 1468850 |
| Reference:
|
[58] RANDBY S. P.: Minimal embeddings in the projective plane.Preprint, 1995. MR 1448852 |
| Reference:
|
[59] RICHTER R. B.-VITRAY R.: On the existence of essential cycles in embedded graphs.Preprint, 1992. |
| Reference:
|
[60] RICHTER R. B.-VITRAY R.: On essential and inessential polygons in embedded graphs.Preprint, 1994. MR 1877903 |
| Reference:
|
[61] RISKIN A.: On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle.Preprint, 1994. MR 1826821 |
| Reference:
|
[62] RISKIN A.-BARNETTE D. W.: On the noninterpolation of polyhedral maps.Discrete Math. 131 (1994), 211-219. Zbl 0806.05030, MR 1287735 |
| Reference:
|
[63] ROBERTSON N.-SEYMOUR P. D.: Graph minors. VII. Disjoint paths on a surface.J. Combin. Theory Ser. B 45 (1988), 212-254. Zbl 0658.05044, MR 0961150 |
| Reference:
|
[64] ROBERTSON N.-SEYMOUR P. D.: Graph minors. XX. Wagner's conjecture.(In preparation). Zbl 1061.05088 |
| Reference:
|
[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 1224699 |
| Reference:
|
[66] ROBERTSON N.-THOMAS R.: On the orientable genus of graphs embedded in the Klein bottle.J. Graph Theory 15 (1991), 407-419. Zbl 0735.05031, MR 1118042 |
| Reference:
|
[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 1083384 |
| Reference:
|
[68] ROBERTSON N.-ZHA X.-ZHAO Y.: On the uniqueness of embeddings of graphs in the torus.Preprint, 1995. |
| Reference:
|
[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. Zbl 0732.90087, MR 1083385 |
| Reference:
|
[70] SCHRIJVER A.: Disjoint circuits of prescribed homotopies in a graph on a compact surface.J. Combin. Theory Ser. B 51 (1991), 127-159. Zbl 0723.05050, MR 1088630 |
| Reference:
|
[71] SCHRIJVER A.: Decomposition of graphs on surfaces and a homotopic circulation theorem.J. Combin. Theory Ser. B 51 (1991), 161-210. Zbl 0723.05051, MR 1099070 |
| Reference:
|
[72] SCHRIJVER A.: Circuits in graphs embedded on the torus.Discrete Math. 106/107 (1992), 415-433. Zbl 0760.05031, MR 1181939 |
| Reference:
|
[73] SCHRIJVER A.: On the uniqueness of kernels.J. Combin. Theory Ser. B 55 (1992), 146-160. Zbl 0810.05023, MR 1159861 |
| Reference:
|
[74] SCHRIJVER A.: Graphs on the torus and geometry of numbers.J. Combin. Theory Ser. B 58 (1993), 147-158. Zbl 0794.05023, MR 1214894 |
| Reference:
|
[75] SCHRIJVER A.: Classification of minimal graphs of given face-width on the torus.J. Combin. Theory Ser. B 61 (1994), 217-236. Zbl 0809.05036, MR 1280609 |
| Reference:
|
[76] SEYMOUR P. D.-THOMAS R.: Uniqueness of highly representative surface embeddings.J. Combin. Theory Ser. B (To appear). Zbl 0863.05028, MR 1418305 |
| Reference:
|
[77] THOMAS R.-YU X.: 4-connected projective planar graphs are Hamiltonian.J. Combin. Theory Ser. B 62 (1994), 114-132. Zbl 0802.05051, MR 1290634 |
| Reference:
|
[78] THOMAS R.-YU X.: 5-connected toroidal graphs are Hamiltonian.J. Combin. Theory Ser. B 69 (1997), 79-96. MR 1426752 |
| Reference:
|
[79] THOMASSEN C.: The graph genus problem is NP-complete.J. Algorithms 10 (1989), 568-576. Zbl 0689.68071, MR 1022112 |
| Reference:
|
[80] THOMASSEN C.: Embeddings of graphs with no short noncontractible cycles.J. Combin. Theory Ser. B 48 (1990), 155-177. Zbl 0704.05011, MR 1046752 |
| Reference:
|
[81] THOMASSEN C.: Triangulating a surface with a prescribed graph.J. Combin. Theory Ser. B 57 (1993), 196-206. Zbl 0794.05025, MR 1207487 |
| Reference:
|
[82] THOMASSEN C.: Five-coloring maps on surfaces.J. Combin. Theory Ser. B 59 (1993), 89-105. Zbl 0794.05026, MR 1234386 |
| Reference:
|
[83] THOMASSEN C.: Trees in triangulations.J. Combin. Theory Ser. B 60 (1994), 56-62. Zbl 0794.05027, MR 1256583 |
| Reference:
|
[84] TUTTE W. T.: A theorem on planar graphs.Trans. Amer. Math. Soc. 82 (1956), 99-116. Zbl 0070.18403, MR 0081471 |
| Reference:
|
[85] VITRAY R.: The 2- and ^3-representative projective planar embeddings.J. Combin. Theory Ser. B 54 (1992), 1-12. MR 1142261 |
| Reference:
|
[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 1224714 |
| Reference:
|
[87] WHITNEY H.: 2-isomorphic graphs.Amer. J. Math. 55 (1933), 245-254. Zbl 0006.37005, MR 1506961 |
| Reference:
|
[88] YU X.: Disjoint paths, planarizing cycles, and k-walks.Preprint, 1993. |
| Reference:
|
[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 1224715 |
| . |
