Information Technology Reference
In-Depth Information
[12] Dujmovic, V., Wood, D.R.: Graph treewidth and geometric thickness parameters.
Discrete Comput. Geom. 37(4), 641-670 (2007), doi:10.1007/s00454-007-1318-7
[13] Ebbinghaus, H.-D., Flum, J., Thomas, W.: Mathematical logic, 2nd edn. Under-
graduate Texts in Mathematics. Springer (1994), doi:10.1007/978-1-4757-2355-7;
Translated from the German by Margit Meßmer
[14] Goldstein, A.J.: An ecient and constructive algorithm for testing whether a
graph can be embedded in a plane. In: Graph and Combinatorics Conference
(1963)
[15] Grohe, M.: Computing crossing numbers in quadratic time. Journal of Computer
and System Sciences 68(2), 285-302 (2004), doi:10.1016/j.jcss.2003.07.008
[16] Kainen, P.C.: Some recent results in topological graph theory. In: Graphs and Com-
binatorics. Lecture Notes in Mathematics, vol. 406, pp. 76-108. Springer (1974),
doi:10.1007/BFb0066436
[17] Kawarabayashi, K., Reed, B.: Computing crossing number in linear time.
In: ACM Symp. Theory of Computing (STOC 2007), pp. 382-390 (2007),
doi:10.1145/1250790.1250848
[18] Mitchell, S.L.: Linear algorithms to recognize outerplanar and maximal outerpla-
nar graphs. Information Processing Letters 9(5), 229-232 (1979), doi:10.1016/0020-
0190(79)90075-9
[19] Ollmann, L.T.: On the topic thicknesses of various graphs. In: Proc. 4th South-
eastern Conference on Combinatorics, Graph Theory and Computing, vol. 8, p.
459 (1973)
[20] Pelsmajer, M.J., Schaefer, M., Stefankovic, D.: Crossing numbers and parameter-
ized complexity. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS,
vol. 4875, pp. 31-36. Springer, Heidelberg (2008), doi:10.1007/978-3-540-77537-
9 6.
[21] Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths
problem. Journal of Combinatorial Theory, Series B 63(1), 65-110 (1995),
doi:10.1006/jctb.1995.1006
[22] Shahrokhi, F., Sykora, O., Szekely, L.A., Vrto, I.: Book embeddings and cross-
ing numbers. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS,
vol. 903, pp. 256-268. Springer, Heidelberg (1995)
[23] Shirey, R.W.: Implementation and Analysis of Ecient Graph Planarity Testing
Algorithms. Ph.D. thesis, The University of Wisconsin - Madison (1969)
[24] Wattenberg, M.: Arc diagrams: visualizing structure in strings. In: IEEE Sym-
posium on Information Visualization (INFOVIS 2002), pp. 110-116 (2002),
doi:10.1109/INFVIS.2002.1173155
[25] Wiegers, M.: Recognizing outerplanar graphs in linear time. In: Tinhofer, G.,
Schmidt, G. (eds.) WG 1986. LNCS, vol. 246, pp. 165-176. Springer, Heidelberg
(1987)
[26] Yannakakis, M.: Four pages are necessary and sucient for planar graphs. In: Proc.
18th ACM Symp. on Theory of Computing (STOC 1986), pp. 104-108 (1986),
doi:10.1145/12130.12141
