Quantcast

Computing Planarity in Computable Planar Graphs

Research paper by Oscar Levin, Taylor McMillan

Indexed on: 11 Nov '16Published on: 01 Nov '16Published in: Graphs and Combinatorics



Abstract

Abstract A graph is computable if there is an algorithm which decides whether given vertices are adjacent. Having a procedure for deciding the edge set might not help compute other properties or features of the graph, however. The goal of this paper is to investigate the extent to which features related to the planarity of a graph might or might not be computable. We propose three definitions for what it might mean for a computable graph to be computably planar and for each build a computable planar graph which fails to be computably planar. We also consider these definitions in the context of highly computable graphs, those for which there is an algorithm which computes the degree of a given vertex.AbstractA graph is computable if there is an algorithm which decides whether given vertices are adjacent. Having a procedure for deciding the edge set might not help compute other properties or features of the graph, however. The goal of this paper is to investigate the extent to which features related to the planarity of a graph might or might not be computable. We propose three definitions for what it might mean for a computable graph to be computably planar and for each build a computable planar graph which fails to be computably planar. We also consider these definitions in the context of highly computable graphs, those for which there is an algorithm which computes the degree of a given vertex.computableplanarityhighly computable graphs