Name
Abstract | ||
|---|---|---|
A non-planar graph G is almost-planar if, for every edge e of G, either G\e or G/e is planar. We provide an algorithmic proof of a theorem by D. K. Wagner, according to which every almost-planar graph can be reduced to the graph K3,3 by some sequence of series/parallel reductions and delta-wye exchanges such that the reduction sequence is formed by almost-planar graphs. We study 3-connected almost-planar graphs on the projective plane and establish duality relations between the resulting families. We show that one family reduces to K3,3 (with an added parallel edge) while the dual family reduces to K5. We also characterize 3-terminal delta-wye reducibility for almost-planar graphs. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.endm.2017.10.023 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
delta-wye reducibility,almost-planar graphs,projective-planar graphs | Discrete mathematics,Outerplanar graph,Indifference graph,Combinatorics,Robertson–Seymour theorem,Forbidden graph characterization,Chordal graph,Pathwidth,1-planar graph,Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
62 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 2 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Isidoro Gitler | 1 | 29 | 7.03 |
| Gustavo Sandoval-Angeles | 2 | 0 | 0.34 |