Genus, Treewidth, and Local Crossing Number

Dujmović, Vida and Eppstein, David and Wood, David R. (2015) Genus, Treewidth, and Local Crossing Number. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 87-98 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_8).

Full text not available from this repository.

Abstract

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O(sqrt((g+1)(k+1)n)) and layered treewidth O((g+1)k), and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth O(sqrt((k+1)n)) and layered treewidth O(k+1), which are tight bounds that improve a previously known O((k+1)^(3/4)n^(1/2)) treewidth bound. Additionally, we show that for g<m, every m-edge graph can be embedded on a surface of genus g with O((m/(g+1))log^(2)g) crossings per edge, which is tight to a polylogarithmic factor.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.001 General
Z Theory > Z.750 Topology
ID Code:1480

Repository Staff Only: item control page

References

Dvorák, Z., Norin, S.: Treewidth of graphs with balanced separations. Electronic preprint arXiv: 1408.​3869 (2014)

Reed, B.A.: Tree width and tangles: a new connectivity measure and some applications. In: Bailey, R.A. (ed.) Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 241, pp. 87–162. Cambridge University Press, Cambridge (1997)

Schaefer, M.: The graph crossing number and its variants: a survey. Electron. J. Combin. DS21 (2014)

Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)

Guy, R. K., Jenkyns, T., Schaer, J.: The toroidal crossing number of the complete graph. J. Comb. Theor. 4, 376–390 (1968)

Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J. Algorithms 5(3), 391–407 (1984)

Dujmović, V., Morin, P., Wood, D.R.: Layered separators in minor-closed families with applications. Electronic preprint arXiv: 1306.​1595 (2013)

Shahrokhi, F., Székely, L.A., Sýkora, O., Vrt’o, I.: Drawings of graphs on surfaces with few crossings. Algorithmica 16(1), 118–131 (1996)

Halin, R.: S-functions for graphs. J. Geometry 8(1–2), 171–186 (1976)

Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)

Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275–291 (2000)

Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439–561 (2006)

Grohe, M., Marx, D.: On tree width, bramble size, and expansion. J. Combin. Theory Ser. B 99(1), 218–228 (2009)

Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999)