Alternating plane graphs - Althöfer, Ingo (Ars mathematica contemporanea, 2015)
Ravninski graf se imenuje alternirajoč, če imajo vsa sosednja vozlišča različne stopnje, prav tako pa tudi vsa sosednja lica. Alternirajoče ravninske grafe so prvič obravnavali leta 2008. Ta članek povzema dosedanje raziskave o alternirajočih ravninskih grafih. Obstajata dva najmanjša alternirajoča ravninska grafa, vsak od njiju ima po 17 vozlič in 17 lic. Ni nobenega alternirajočega ravninskega grafa na 18 vozliščih, obstajajo pa alternirajoči ravninski grafi za vse grafe na 19 ali več vozliščih. Iz majhne množice začetnih gradnikov lahko konstruiramo alternirajoče ravninske grafe za vse grafe večjih redov. Veliko majhnih alternirajočih ravninskih grafov so našli z izdatno pomočjo računalnikov. V članek so vključeni teoretični rezultati o alternirajočih ravninskih grafih, v katerih so vse stopnje vozlišč elementi množice ?$\{3,4,5\}$?. Predstavljenih je tudi več razredov "šibko alternirajočih ravninskih grafov" (z vozlišči stopnje 2).
Keywords: alternating degrees; alternirajoče stopnje; exhaustive search; heuristic search; hevristično iskanje; izčrpno iskanje; plane graph; ravninski grafi