Name
Abstract | ||
|---|---|---|
A nonplanar graph G is almost-planar if, for every edge e of G, either G∖e or G∕e is planar. The class of almost-planar graphs were introduced in 1990 by Gubser. In 2015, Wagner proved that every almost-planar graph is delta–wye reducible to K3,3. Moreover, he showed that there exists a reduction sequence in which every graph is almost-planar. We obtain an O(n2) algorithm for Wagner’s result. We also prove that simple, 3-connected, almost-planar graphs have crossing number one and furthermore that these graphs are 3-terminal delta–wye reducible to K6 minus the edges of a triangle, whose vertices are taken as terminals. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2020.06.024 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Delta–wye transformations,Almost-planar graphs,Delta–wye reducibility,Crossing number | Journal | 285 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Isidoro Gitler | 1 | 29 | 7.03 |
| Gustavo Sandoval–Angeles | 2 | 0 | 0.34 |