Open AccessEmbedding Non-planar Graphs: Storage and Representation
Author(s) -
Ðorže Klisura
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.18690/978-961-286-516-0.13
Subject(s) - book embedding , planar graph , computer science , embedding , codebase , topological graph theory , chordal graph , vertex (graph theory) , theoretical computer science , string (physics) , pathwidth , discrete mathematics , combinatorics , 1 planar graph , graph , mathematics , line graph , programming language , artificial intelligence , source code , mathematical physics
In this paper, we propose a convention for repre-senting non-planar graphs and their least-crossing embeddings in a canonical way. We achieve this by using state-of-the-art tools such as canonical labelling of graphs, Nauty’s Graph6 string and combinatorial representations for planar graphs. To the best of our knowledge, this has not been done before. Besides, we implement the men-tioned procedure in a SageMath language and compute embeddings for certain classes of cubic, vertex-transitive and general graphs. Our main contribution is an extension of one of the graph data sets hosted on MathDataHub, and towards extending the SageMath codebase.