Drawing non-planar graphs with rotation systems on the Klein bottle

2023/07/17 by Doré, François, Formenti, Enrico
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2307.08287

Abstract

This paper provides a linear time algorithm in the number of edges that, given a simple 3-connected non-planar graph G with a Klein bottle rotation system, outputs a straight line drawing of G with no crossings on the flat Klein bottle.

Related

• Drawing disconnected graphs on the Klein bottle
• Algorithmic methods of finite discrete structures. Topological graph drawing (part IV)
• Algorithmic methods of finite discrete structures. Topological graph drawing (part I)
• Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time
• Non-aligned drawings of planar graphs