Information Technology Reference
In-Depth Information
Dujmovic and Wood asked [ ? ], “is there a polynomial-time algorithm for com-
puting the topic thickness of graphs with bounded treewidth?” Our Theorem 2
provides a partial solution to this question for topic thickness 2. Can the graph
property of having topic thickness k beexpressedinMSO 2 , answering the ques-
tion of Dujmovic and Wood? The special case of k = 3 is of particular interest,
to provide a computational attack on the still-open problem of whether there
exist planar graphs that require four pages [12,26]. Heath has shown that every
planar graph of treewidth three has a planar 3-page drawing [ ? ], but recognizing
three-page graphs of higher treewidth eciently remains open.
Acknowledgments. This material is based upon work supported by the Na-
tional Science Foundation under Grant CCF-1228639 and by the Oce of Naval
Research under Grant No. N00014-08-1-1015.
References
[1] Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embeddings in
a k -tree. SIAM J. Alg. Disc. Meth. 8(2), 277-284 (1987), doi:10.1137/0608024
[2] Auslander, L., Parter, S.V.: On imbedding graphs in the sphere. Journal of Math-
ematics and Mechanics 10(3), 517-523 (1961)
[3] Bannister, M.J., Eppstein, D., Simons, J.A.: Fixed parameter tractability of cross-
ing minimization of almost-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS,
vol. 8242, pp. 340-351. Springer, Heidelberg (2013), doi:10.1007/978-3-319-03841-
4 30
[4] Bernhart, F., Kainen, P.C.: The topic thickness of a graph. Journal of Combina-
torial Theory, Series B 27(3), 320-331 (1979), doi:10.1016/0095-8956(79)90021-2
[5] Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions
of small treewidth. In: Proceedings of the Twenty-fifth Annual ACM Sym-
posium on Theory of Computing, STOC 1993, pp. 226-234. ACM (1993),
doi:10.1145/167088.167161
[6] Bodlaender, H.L.: A partial k -arboretum of graphs with bounded treewidth. Theo-
retical Computer Science 209(1-2), 1-45 (1998), doi:10.1016/S0304-3975(97)00228-
4
[7] Chartrand, G., Harary, F.: Planar permutation graphs. Annales de l'institut
Henri Poincare (B) Probabilites et Statistiques 3(4), 433-438 (1967),
http://eudml.org/doc/76875
[8] Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: A
layout problem with applications to VLSI design. SIAM J. Alg. Disc. Meth. 8(1),
33-58 (1987), doi:10.1137/0608002
[9] Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of
finite graphs. Information and Computation 85(1), 12-75 (1990), doi:10.1016/0890-
5401(90)90043-H
[10] Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic:
A Language-Theoretic Approach. Cambridge University Press (2012)
[11] Dujmovic, V., Fellows, M.R., Kitching, M., Liotta, G., McCartin, C., Nishimura,
N., Ragde, P., Rosamond, F., Whitesides, S., Wood, D.R.: On the parameter-
ized complexity of layered graph drawing. Algorithmica 52(2), 267-292 (2008),
doi:10.1007/s00453-007-9151-1
 
Search WWH ::




Custom Search