Advanced search
1 file | 433.75 KB
Author
Organization
Project
HPC-UGent: the central High Performance Computing infrastructure of Ghent University
Abstract
A plane graph is called alternating if all adjacent vertices have different degrees, and all neighboring faces as well. Alternating plane graphs were introduced in 2008. This paper presents the previous research on alternating plane graphs. There are two smallest alternating plane graphs, having 17 vertices and 17 faces each. There is no alternating plane graph with 18 vertices, but alternating plane graphs exist for all cardinalities from 19 on. From a small set of initial building blocks, alternating plane graphs can be constructed for all large cardinalities. Many of the small alternating plane graphs have been found with extensive computer help. Theoretical results on alternating plane graphs are included where all degrees have to be from the set {3,4,5}. In addition, several classes of “weak alternating plane graphs” (with vertices of degree 2) are presented.
Keywords
alternating degrees, Plane graph, exhaustive search, heuristic search

Downloads

  • 584-3877-1-PB.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 433.75 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Althöfer, Ingo, Jan Kristian Haugland, Karl Scherer, Frank Schneider, and Nicolas Van Cleemput. 2015. “Alternating Plane Graphs.” Ars Mathematica Contemporanea 8 (2): 337–363.
APA
Althöfer, I., Haugland, J. K., Scherer, K., Schneider, F., & Van Cleemput, N. (2015). Alternating plane graphs. ARS MATHEMATICA CONTEMPORANEA, 8(2), 337–363.
Vancouver
1.
Althöfer I, Haugland JK, Scherer K, Schneider F, Van Cleemput N. Alternating plane graphs. ARS MATHEMATICA CONTEMPORANEA. 2015;8(2):337–63.
MLA
Althöfer, Ingo, Jan Kristian Haugland, Karl Scherer, et al. “Alternating Plane Graphs.” ARS MATHEMATICA CONTEMPORANEA 8.2 (2015): 337–363. Print.
@article{6921573,
  abstract     = {A plane graph is called alternating if all adjacent vertices have different degrees, and all neighboring faces as well. Alternating plane graphs were introduced in 2008. This paper presents the previous research on alternating plane graphs.
There are two smallest alternating plane graphs, having 17 vertices and 17 faces each. There is no alternating plane graph with 18 vertices, but alternating plane graphs exist for all cardinalities from 19 on. From a small set of initial building blocks, alternating plane graphs can be constructed for all large cardinalities. Many of the small alternating plane graphs have been found with extensive computer help.
Theoretical results on alternating plane graphs are included where all degrees have to be from the set \{3,4,5\}. In addition, several classes of {\textquotedblleft}weak alternating plane graphs{\textquotedblright} (with vertices of degree 2) are presented.},
  author       = {Alth{\"o}fer, Ingo and Haugland, Jan Kristian and Scherer, Karl and Schneider, Frank and Van Cleemput, Nicolas},
  issn         = {1855-3966},
  journal      = {ARS MATHEMATICA CONTEMPORANEA},
  keyword      = {alternating degrees,Plane graph,exhaustive search,heuristic search},
  language     = {eng},
  number       = {2},
  pages        = {337--363},
  title        = {Alternating plane graphs},
  url          = {http://amc-journal.eu/index.php/amc/article/view/584},
  volume       = {8},
  year         = {2015},
}

Web of Science
Times cited: