Face-width of embedded graphs

 Access to full text

 Full (PDF)

1. ALTSCHULER A., Hamiltonian circuits in some maps on the torus, Discrete Math. 1 (1972), 299-314. (1972) MR0297597
2. ARCHDEACON D., Densely embedded graphs, J. Combin, Theory Ser. B 54 (1992), 13-36. (1992) Zbl0694.05024MR1142262
3. ARCHDEACON D.-RICHTER R. B., Construction and classification of self-dual spherical polyhedra, J. Combin. Theory Ser. B 54 (1992), 37-63. (1992) MR1142263
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. (1996) MR1405705
5. AUSLANDER L.-BROWN I. A.-YOUNGS J. W. T., The imbedding of graphs in manifolds, J. Math. Mech. 12 (1963), 629-634. (1963) Zbl0115.40804MR0151959
6. BARNETTE D., Trees in polyhedral graphs, Canad. J. Math. 18 (1966), 731-736. (1966) Zbl0141.21401MR0195753
7. BARNETTE D., Generating the triangulations of the projective plane, J. Combin. Theory Ser. B 33 (1982), 222-230. (1982) Zbl0509.52007MR0693361
8. BARNETTE D. W., Generating closed 2-cell embeddings in the torus and the projective plane, Discrete Comput. Geom. 2 (1987), 233-247. (1987) Zbl0614.51008MR0892170
9. BARNETTE D. W., Decomposition theorems for the torus projective plane and Klein bottle, Discrete Math. 70 (1988), 1-16. (1988) Zbl0654.05024MR0943718
10. BARNETTE D. W., Unique embeddings of simple projective plane polyhedral maps, Israel J. Math. 67 (1989), 251-256. (1989) Zbl0694.05030MR1026567
11. BARNETTE D. W., Generating projective plane polyhedral maps, J. Combin. Theory Ser. B 51 (1991), 277-291. (1991) Zbl0722.05029MR1099077
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. (1991) Zbl0803.52008MR1116338
13. BARNETTE D. W., n-chain embeddings in the projective plane, torus and Klein bottle, Preprint, 1991. (1991) MR1119930
14. BARNETTE D. W., 3-trees in polyhedral maps, Israel. J. Math. 79 (1992), 251-256. (1992) Zbl0770.05041MR1248916
15. BARNETTE D., 2-connected spanning subgraphs of planar 3-connected graphs, J. Combin. Theory Ser. B 61 (1994), 210-216. (1994) Zbl0812.05015MR1280608
16. BARNETTE D. W.-RISKIN A., Polyhedral and closed 2-cell embeddings in manifolds, Preprint, 1991. (1991) 
17. BENDER E. A.-GAO Z.-RICHMOND L. B., Almost all rooted maps have large representativity, J. Graph Theory 18 (1994), 545-555. (1994) Zbl0809.05060MR1292974
18. BONDY J. A.-MURTY U. S. R., Graph Theory with Applications, North- Holland, New York, 1981. (1981) 
19. BRIGHTWELL G. R.-SCHEINERMAN E. R., Representations of planar graphs, SIAM J. Discrete Math. 6 (1993), 214-229. (1993) Zbl0782.05026MR1215229
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. (1995) Zbl0837.05049MR1347338
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. (1996) Zbl0855.05048MR1376046
22. ELLINGHAM M. N.-GAO Z., Spanning trees in locally planar triangulations, J. Combin. Theory Ser. B 61 (1994), 178-198. (1994) Zbl0802.05033MR1280606
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. (1995) Zbl0837.05051MR1355428
24. GAO Z. C., 2-connected coverings of bounded degree in 3-connected graphs, J. Graph Theory 20 (1995), 327-338. (1995) Zbl0838.05034MR1355432
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. (1991) 
26. GAO Z. C.-RICHTER R. B., 2-walks in circuit graphs, J. Combin. Theory Ser. B 62 (1994), 259-267. (1994) Zbl0807.05027MR1305052
27. GAO Z.-RICHTER R. B.-SEYMOUR P. D., Irreducible triangulations of surfaces, J. Combin. Theory Ser. B 68 (1996), 206-217. (1996) Zbl0863.05029MR1417796
28. GAO Z. C.-RICHTER R. B.-YU X., 2-walks in planar 3-connected graphs, Australas. J. Combin. 11 (1995), 117-122. (1995) MR1327325
29. GAO Z. C,. WORMALD N. C., Spanning Eulerian subgraphs of bounded degree in triangulations, Graphs Combin. 10 (1994), 123-131. (1994) MR1289970
30. de GRAAF M., Graphs and Curves on Surfaces, Ph. D. Thesis, University of Amsterdam, Amsterdam, 1994. (1994) 
31. de GRAAF M.-SCHRIJVER A., Grid minors of graphs on the torus, J. Com- bin. Theory Ser. B 61 (1994), 57-62. (1994) Zbl0809.05037MR1275263
32. GROSS J. L.-TUCKER T. W., Topological Graph Theory, Wiley Interscience, New York, 1987. (1987) Zbl0621.05013MR0898434
33. HUTCHINSON J., On short noncontractible cycles in embedded graphs, SIAM J. Discrete Math. 1 (1988), 185-192. (1988) Zbl0663.05025MR0941349
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. (1989) Zbl0682.68049MR1006473
35. HUTCHINSON J. P., Three-coloring graphs embedded on surfaces with all faces even-sided, J. Combin. Theory Ser. B 65 (1995), 139-155. (1995) Zbl0828.05029MR1347344
36. JUVAN M.-MALNIC A.-MOHAR B., Systems of curves on surfaces, J. Combin. Theory Ser. B 68 (1996), 7-22. (1996) Zbl0859.57014MR1405702
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. (1987) Zbl0618.05019MR0900052
38. LAWRENCHENKO S., The variety of triangular embeddings of a graph in the projective plane, J. Combin. Theory Ser. B 54 (1992), 196-208. (1992) MR1152447
39. LAWRENCENKO S.-NEGAMI S., Constructing the graphs that triangulate both the torus and the Klein bottle, Preprint, 1994. (1994) 
40. LINS S., A minimax theorem on circuits in projective graphs, J. Combin. Theory Ser. B 30 (1981), 253-262. (1981) Zbl0401.05067MR0624541
41. MALNIC A.-MOHAR B., Generating locally cyclic triangulations of surfaces, J. Combin. Theory Ser. B 56 (1992), 147-164. (1992) Zbl0723.05053MR1186752
42. MALNIC A.-NEDELA R., k-Minimal triangulations of surfaces, Acta Math. Univ. Comenian. 64 (1995), 57-76. (1995) Zbl0921.05029MR1360987
43. MOHAR B., Combinatorial local planarity and the width of graph embeddings, Canad. J. Math. 44 (1992), 1272-1288. (1992) Zbl0777.05052MR1192418
44. MOHAR B., Uniqueness and minimality of large face-width embeddings of graphs, Combinatorica 15 (1995), 541-556. (1995) Zbl0838.05041MR1364026
45. MOHAR B., Apex graphs with embeddings of face-width three, Discrete Math. (To appear). Zbl0891.05026MR1477290
46. MOHAR B., On the orientable genus of graphs with bounded nonorientable genus, Manuscript, 1995. (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. (1993) Zbl0792.05046MR1221805
48. MOHAR B.-ROBERTSON N., Disjoint essential cycles, J. Combin. Theory Ser. B 68 (1996), 324-349. (1996) Zbl0861.05038MR1417805
49. MOHAR B.-ROBERTSON N., Planar graphs on nonplanar surfaces, J. Combin. Theory Ser. B 68 (1996), 87-111. (1996) Zbl0856.05027MR1405707
50. MOHAR B.-ROBERTSON N.-VITRAY R. P., Planar graphs on the projective plane, Discrete Math. 149 (1996), 141-157. (1996) Zbl0849.05023MR1375105
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. (1995) MR1337505
52. MOHAR B.-THOMASSEN C., Graphs on Surfaces, Johns Hopkins Univ. Press (To appear). Zbl1230.05133MR1844449
53. NAKAMOTO A.-OTA K., Vote on irreducible triangulations of surfaces, J. Graph Theory 20 (1995), 227-233. (1995) MR1348564
54. NEGAMI S., Uniqueness and faithfulness of embedding of toroidal graphs, Discrete Math. 44 (1983), 161-180. (1983) Zbl0508.05033MR0689809
55. NEGAMI S., Unique and faithful embeddings of projective-planar graphs, J. Graph Theory 9 (1985), 235-243. (1985) Zbl0578.05017MR0797512
56. NEGAMI S., Re-embedding of projective-planar graphs, J. Combin. Theory Ser. B 44 (1988), 276-299. (1988) Zbl0609.05033MR0941437
57. PRZYTYCKA T.-PRZYTYCKI J. H., A simple construction of high representativity triangulations, Preprint, 1993. (1993) MR1468850
58. RANDBY S. P., Minimal embeddings in the projective plane, Preprint, 1995. (1995) MR1448852
59. RICHTER R. B.-VITRAY R., On the existence of essential cycles in embedded graphs, Preprint, 1992. (1992) 
60. RICHTER R. B.-VITRAY R., On essential and inessential polygons in embedded graphs, Preprint, 1994. (1994) MR1877903
61. RISKIN A., On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle, Preprint, 1994. (1994) MR1826821
62. RISKIN A.-BARNETTE D. W., On the noninterpolation of polyhedral maps, Discrete Math. 131 (1994), 211-219. (1994) Zbl0806.05030MR1287735
63. ROBERTSON N.-SEYMOUR P. D., Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory Ser. B 45 (1988), 212-254. (1988) Zbl0658.05044MR0961150
64. ROBERTSON N.-SEYMOUR P. D., Graph minors. XX. Wagner's conjecture, (In preparation). Zbl1061.05088
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. (1991) MR1224699
66. ROBERTSON N.-THOMAS R., On the orientable genus of graphs embedded in the Klein bottle, J. Graph Theory 15 (1991), 407-419. (1991) Zbl0735.05031MR1118042
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. (1990) MR1083384
68. ROBERTSON N.-ZHA X.-ZHAO Y., On the uniqueness of embeddings of graphs in the torus, Preprint, 1995. (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. (1990) Zbl0732.90087MR1083385
70. SCHRIJVER A., Disjoint circuits of prescribed homotopies in a graph on a compact surface, J. Combin. Theory Ser. B 51 (1991), 127-159. (1991) Zbl0723.05050MR1088630
71. SCHRIJVER A., Decomposition of graphs on surfaces and a homotopic circulation theorem, J. Combin. Theory Ser. B 51 (1991), 161-210. (1991) Zbl0723.05051MR1099070
72. SCHRIJVER A., Circuits in graphs embedded on the torus, Discrete Math. 106/107 (1992), 415-433. (1992) Zbl0760.05031MR1181939
73. SCHRIJVER A., On the uniqueness of kernels, J. Combin. Theory Ser. B 55 (1992), 146-160. (1992) Zbl0810.05023MR1159861
74. SCHRIJVER A., Graphs on the torus and geometry of numbers, J. Combin. Theory Ser. B 58 (1993), 147-158. (1993) Zbl0794.05023MR1214894
75. SCHRIJVER A., Classification of minimal graphs of given face-width on the torus, J. Combin. Theory Ser. B 61 (1994), 217-236. (1994) Zbl0809.05036MR1280609
76. SEYMOUR P. D.-THOMAS R., Uniqueness of highly representative surface embeddings, J. Combin. Theory Ser. B (To appear). Zbl0863.05028MR1418305
77. THOMAS R.-YU X., 4-connected projective planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994), 114-132. (1994) Zbl0802.05051MR1290634
78. THOMAS R.-YU X., 5-connected toroidal graphs are Hamiltonian, J. Combin. Theory Ser. B 69 (1997), 79-96. (1997) MR1426752
79. THOMASSEN C., The graph genus problem is NP-complete, J. Algorithms 10 (1989), 568-576. (1989) Zbl0689.68071MR1022112
80. THOMASSEN C., Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory Ser. B 48 (1990), 155-177. (1990) Zbl0704.05011MR1046752
81. THOMASSEN C., Triangulating a surface with a prescribed graph, J. Combin. Theory Ser. B 57 (1993), 196-206. (1993) Zbl0794.05025MR1207487
82. THOMASSEN C., Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993), 89-105. (1993) Zbl0794.05026MR1234386
83. THOMASSEN C., Trees in triangulations, J. Combin. Theory Ser. B 60 (1994), 56-62. (1994) Zbl0794.05027MR1256583
84. TUTTE W. T., A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99-116. (1956) Zbl0070.18403MR0081471
85. VITRAY R., The 2- and ^3-representative projective planar embeddings, J. Combin. Theory Ser. B 54 (1992), 1-12. (1992) MR1142261
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. (1991) MR1224714
87. WHITNEY H., 2-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254. (1933) Zbl0006.37005MR1506961
88. YU X., Disjoint paths, planarizing cycles, and k-walks, Preprint, 1993. (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. (1991) MR1224715

1. Stanislav Jendrol', Heinz-Jürgen Voss, Light classes of generalized stars in polyhedral maps on surfaces
2. Stanislav Jendroľ, Roman Nedela, Martin Škoviera, Constructing regular maps and graphs from planar quotients