M Yannakakis
- BC.F. Bernhart and B. Kainen, "The book thickness of a graph", L Combinatorial Theory B, 27,320-331, (1979).Google Scholar
Cross Ref
- BS.J. F. Buss, and P. W. Shot, non the pagenumber of planar graphs', Prec. 16th Ann. ACM Syrup. on Theory of Computing, 98-100, (1984). Google ScholarDigital Library
- CLR1.F. R. K. Chung, F. T. LeighWn, and A. L. Rosenberg, "Diogenes: a methodology for designing fanlt-tolerant VLSI processor arrays", 13th Int'l ConL on Fault-tolerant Computing, 26-32, (1983).Google Scholar
- CLR2.F. R. K. Chung, F. T. Leighton, and A.L. Rosenberg, "A graph layout problem with applications to VLSI design", (1984).Google Scholar
- EI.S. Even, and A. Itai, "Queues, stacks and graphs', in Theory of Machines and Computations, Z. Kohavi and A. Paz, eds., Academic Press, NY, 71-86, (1971).Google Scholar
- GJMP.M. R. Garey, D. S. Johnson, G. L. Miner, and C. I-I. Papadimitriou, "The complexity of coloring circular arcs and chords', SIAM J. on Alg. and Disc. Meth., I, 216- 227, (1980).Google ScholarCross Ref
- H.L. Heath, "Embedding planar graphs in seven pages", Prec. 25th Ann. Syrup. on Foundations of Computer Science, 74-83, (1984).Google Scholar
- R.A. L. Rosenberg, "The Diogenes Approach to testable fault-tolerant arrays of processors", IEEE Trans. on Computing, C-32, 902-910, (1983).Google ScholarDigital Library
- T.R. E. Tarjan, "Sorting using networks of que~aes and stacks", J. Assoc. Comp. Mach., 19, 341-346, (1972). Google ScholarDigital Library
- W.A. Wigderson, "The complexity of the Hamlltonian circuit problem for planar graphs", Princeton Univ. Tech. Report.Google Scholar
Index Terms
- Four pages are necessary and sufficient for planar graphs
Recommendations
A Sufficient Condition for Planar Graphs
A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L-list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for ...
Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate
AbstractA graph G is k-degenerate if every subgraph of G has a vertex of degree at most k. It is known that every planar graph of girth 6 (equivalently, without 3-, 4-, and 5-cycles) is 2-degenerate. On the other hand, there exist planar ...
A sufficient condition for planar graphs to be (3, 1)-choosable
A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying $$|L(x)\cap L(y)|\le d$$|L(x)źL(y)|≤d for each edge xy. An L-coloring is a vertex coloring $$\pi $$ź such that $$\pi (v) \in L(...
Comments