Alternating plane graphs

Authors

  • Ingo Althöfer Friedrich-Schiller Universität
  • Jan Kristian Haugland
  • Karl Scherer
  • Frank Schneider
  • Nico Van Cleemput University Of West Bohemia

DOI:

https://doi.org/10.26493/1855-3974.584.09a

Keywords:

Plane graph, alternating degrees, exhaustive search, heuristic search.

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.

Author Biography

Ingo Althöfer, Friedrich-Schiller Universität

Department of Mathematics and Computer Science

Published

2015-05-27

Issue

Section

Articles