The Effect of Planarization on Width.

Eppstein, David (2017) The Effect of Planarization on Width. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 560-574(Official URL: https://doi.org/10.1007/978-3-319-73915-1_43).

Full text not available from this repository.

Abstract

We study the effects of planarization (the construction of a planar diagram D from a non-planar graph G by replacing each crossing by a new vertex) on graph width parameters. We show that for treewidth, pathwidth, branchwidth, clique-width, and tree-depth there exists a family of n-vertex graphs with bounded parameter value, all of whose planarizations have parameter value Ω(n). However, for bandwidth, cutwidth, and carving width, every graph with bounded parameter value has a planarization of linear size whose parameter value remains bounded. The same is true for the treewidth, pathwidth, and branchwidth of graphs of bounded degree.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.840 Planarization
Z Theory > Z.750 Topology
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1631

Actions (login required)

View Item View Item