Geodesic
The Effect of Planarization on Width
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-fifth International Symposium on Graph Drawing and Network Visualization, GD 2017 , Tome 22 (2018) no. 3, pp. 461-481.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We study the effects on graph width parameters of planarization, the construction of a planar diagram from a non-planar graph drawing by replacing each crossing with a new vertex. 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 $\Omega(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. To show our lower bounds on the width of planarizations, we prove that arrangements of curves with many crossing pairs of curves must generate planar graphs of high width.
DOI : 10.7155/jgaa.00468
Keywords: planarization, complete bipartite graph, treewidth, pathwidth, branchwidth, clique-width, tree-depth, bandwidth, cutwidth, carving width, crossing number 
@article{JGAA_2018_22_3_a3,
     author = {David Eppstein},
     title = {The {Effect} of {Planarization} on {Width}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {461--481},
     publisher = {mathdoc},
     volume = {22},
     number = {3},
     year = {2018},
     doi = {10.7155/jgaa.00468},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00468/}
}
TY  - JOUR
AU  - David Eppstein
TI  - The Effect of Planarization on Width
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 461
EP  - 481
VL  - 22
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00468/
DO  - 10.7155/jgaa.00468
LA  - en
ID  - JGAA_2018_22_3_a3
ER  - 
%0 Journal Article
%A David Eppstein
%T The Effect of Planarization on Width
%J Journal of Graph Algorithms and Applications
%D 2018
%P 461-481
%V 22
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00468/
%R 10.7155/jgaa.00468
%G en
%F JGAA_2018_22_3_a3
David Eppstein. The Effect of Planarization on Width. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-fifth International Symposium on Graph Drawing and Network Visualization, GD 2017
					, Tome 22 (2018) no. 3, pp. 461-481. doi : 10.7155/jgaa.00468. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00468/

Cité par Sources :